本质：二进制拆分。然后是一个配凑。

合起来就是边二进制拆分，边配凑。

快速乘（其实龟速）：把乘数二进制拆分。利用乘法分配率。

用途：防止爆long long

代码：

ll qk(ll x,ll y,ll mod){
    ll ret=0;
    while(y){
        if(y&1) (ret+=x)%=mod;
        (x+=x)%=mod;
        y>>=1;
    }
    return ret;
}

如果为了卡常，可以写成这样：

ll qk(ll x,ll y,ll mod){
    ll ret=0;
    x%=mod;y%=mod;
    while(y){
        if(y&1) ret=ret+x>=mod?ret+x-mod:ret+x;
        x=x+x>=mod?x+x-mod:x+x;
        y>>=1;
    }
    return ret;
}

第一行必须有x%=mod,y%=mod，否则开始x，y可能很大，减一次mod不能减到mod以下。

还是错过几次。。。

（有时候卡这个取模还是挺有效的。）

快速幂（真的快速）：把指数二进制拆分。利用：a^(x+y)=a^x*a^y

用途：各种指数运算，一般还取模。

推广：矩阵快速幂。

代码略。

快速幂经常与快速乘结合。log^2n也是可以接受的。

例题：

随机数生成器

直接推式子，然后分治求等比数列，爆long long，要快速乘。

复杂度：O(log^3n)

[学习笔记]快速幂&&快速乘

原文：https://www.cnblogs.com/Miracevin/p/9734292.html