大数取幂的算法

转载自：https://www.ctolib.com/topics-56300.html

---

1. 幂取模

幂取模是求num^power%MOD的问题。存在取余公式

（a * b） % p = （a%p * b%p） % p

幂为乘积的累积，因此有

int fastMod(int num, int power, int mod) { long long result = num; long long tmp = 1; while (power > 0) { if (power & 1) { // 如果幂为奇数，再乘一次 tmp = (tmp % mod) * (result % mod) % mod; } result = (result % mod) * (result % mod) % mod; power /= 2; } return result; }

---

2. 大数取幂

大数取幂的原理基于取余公式

(a + b) % q = (a%q + b%q) % q

例如，求(10 * 33^3 + 9 * 33^2 + 8 * 33 + 7) % MOD

int nums[4] = {10, 9, 8, 7}; int results = 0; int power = 33; for (int i = 0; i < nums.size(); ++i) { results = (results * power + nums[i]) % MOD; }

转载于:https://www.cnblogs.com/kovu/p/7282981.html