快速幂

原理：

\(a^{13}=a^8\times a^4\times a^1\)

将b不断>>1 同时a不断自我^2 使用b&1判断b的二进制 最后一位是否为1

快速幂

给你三个整数 \(a,b,p\)，求 \(a^b \bmod p\)。

对于 \(100\%\) 的数据，保证 \(0\le a,b < 2^{31}\)，\(a+b>0\)，\(2 \leq p \lt 2^{31}\)。

模板

int ksm(int c,int k,int p) {    //c^k %p
    int res=1;
    while(k) {
        if(k&1)res=res*c%p; //注意只有1句在里面！
        k>>=1;  //不要写反了！
        c=c*c%p;
    }
    return res;
}

另外一种写法？(有误！)

int ksm(int a,int b,int p){
    if(!b)return 1;
    if(b%2)return (a*ksm(a*a%p,b/2,p)%p)%p;
    return (ksm(a*a%p,b/2,p)%p);
} 

另一种写法是std

int ksm(int a,int b){
    if(b==0) return 1;
    if(b==1) return a%MOD;
    int res=ksm(a,b/2);
    res=(res*res)%MOD;
    if(b%2==1) res=(res*a)%MOD;
    return res;
}

光速幂

光速幂和矩阵光速幂 - Lovaer - 博客园

快速幂更通用，而光速幂只能用于同底同模时的多次询问。——分块大法好。

龟速乘

如果我们要两个1e18的数相乘，必然会爆long long，对于这种问题，我们的解法有两个，一个是高精度，另一个就是龟速乘。

算法介绍

先说一个很简单的思路，我们让结果加上 b 个 a，这样每次我们再加的同时来mod上p，那必然可以算出结果。但是b的范围会很大，10e18的数据量是肯定会超时的，为了解决这个问题，我们可以用龟速乘算法。

龟速乘就是来优化我们的加法，每次我们不是一次加一个a，而是每次加上 2 * a 个 a，比如：\(a ,2a,4a,8a… 2^na\).

我们在来看b，从b的二进制表示来说，b从二进制转化为十进制，就是和龟速乘类似的计算方式，比如b的二进制表示为(10110)则，b = 24 + 22 + 21, 因此我们结果就是 a * (24 + 22 + 21),而b的二进制位数最多只有64位，因此，时间复杂度只有为O(64)，完美解决超时的情况。

扩欧定理求快速幂

给你三个正整数，\(a,m,b\)，你需要求：\(a^b \bmod m\)

\(1\le a \le 10^9\)，\(1\le b \le 10^{20000000}，1\le m \le 10^8\)。