快速幂

引入

快速幂是一种效率极高，以至于题目中不得不取模防止数据越界的求幂算法。计算 \(a^n\) 的复杂度为 \(O(\log n)\)。

思想

想一想，如果让你用一种简便的方法计算 \(2^{22}\)，你会怎么做？

\(2^{22}\) 可以转化成 \(2^1*2^2*2^4*2^8*2^7\), 其中的每一项都能用前项步骤直接转化而来，如 \(2^2=2^1*2^1\)，\(2^7=2^4*2^2*2^1\)，只用做 \(\log\) 等级次数的计算。

算法

使用上述思路，我们先考虑 \(n=2^k\) 的情况。

则每次循环 \(a\) 自乘，\(n\) 除以二，有代码：

int ans=1;
while(n){
    a*=a;
    n/=2;
}
ans=a;

\(n\neq2^k\) 时，要考虑 \(n\) 是单数的情况，这时应该 ans*=a，刚好削减 \(n\) 单出来的余数，使我们惊叹该算法精妙的设计：

int ans=1;
while(n){
    if(n%1==1)ans*=a;
    a*=a;
    n/=2;
}

同时我们还可以使用位运算进一步优化：

int ans=1;
while(n){
    if(n&1)ans*=a;
    a*=a;
    n>>=1;
}

完结