【算法】快速幂取模

快速幂

做算法的时候可能会经常遇见对某个数进行指数运算，最简单的就是使用一个循环来解决

int num = 2; int answer = 1; for(int i = 0; i < n; i++) //求2^n { answer *= num; }

更简单粗暴的莫过于

double answer = power(num, n);

但是指数运算是爆炸增长的，当我们的底数和指数足够大的时候，要么发生溢出，要么耗费很长时间

对于溢出的问题我们可以通过取模来解决，实际上对于很大的幂运算我们都会要求对最终答案进行取模，同时根据同余式定理，我们只要对运算过程中的每一个中间结果进行取模运算，就可以避免溢出得问题，最后得到正确的结果

那接下来就要解决时间复杂度的问题，上面所提到的方法有着O(n)的复杂度，这是不够理想的

根据幂运算的性值 当n为偶数时——xⁿ = (x²)^n/2 = (x⁴)^n/4… 当n为奇数时——xⁿ = x * x(²)^(n-1)/2 = x * (x⁴)^n/4… 以此类推

每次我们都把指数除2，底数平方，直到指数为1，这样时间复杂度就变成了O(log2n)，同时加上取模操作

long long fastPower(long long base, long long power, long long mod) { long long result = 1; while(power > 0) { if(power % 2 == 0) { base = (base * base) % mod; power /= 2; } else { power--; result = (result * base) % mod; base = (base * base) % mod; power /= 2; } } return result;//当power=1时,最终的base会被乘到result中 }

这就是基础的代码，还可以继续优化

long long fastPower(long long base, long long power, long long mod) { long long result = 1; while(power > 0) { if(power % 2 == 1) result = (result * base) % mod; power /= 2; base = (base * base) % mod } return result; }