同余和快速幂

这一块一直比较懵逼，所以写一篇分享记录一下。

同余

先介绍同余吧。

同余：对于两个整数$a$和$b$，若它们除以整数$m$所得得余数相等，就称$a$与$b$对于模$m$同余或者$a$同余于$b$模$m$。记作$a \equiv b(mod\quad m)$。

同余的性质
1. 反身性。 $a \equiv a(mod\quad m)$
2. 对称性。 若$a \equiv b(mod\quad m)$，则$b \equiv a(mod\quad m)$
3. 传递性。 若$a \equiv b(mod\quad m)$，$b \equiv c(mod\quad m)$，则$a \equiv c(mod\quad m)$
4. 同余式相加。若$a \equiv b(mod\quad m)$，$c \equiv d(mod\quad m)$，则$a \pm c\equiv b\pm d(mod\quad m)$
5. 同余式相乘。若$a \equiv b(mod\quad m)$，$c \equiv d(mod\quad m)$，则$ac \equiv bd(mod\quad m)$
6. 幂运算。若$a \equiv b(mod\quad m)$，则有$a^{n} \equiv b^{n}(mod\quad m)$

同余性质证明

反身性、对称性以及传递性均可由定义得证。

同余式相加的证明
设$a \% m = b \% m = p$，$c \% m = d \% m = q$，
则有$a = \lfloor a/m \rfloor m + p,b = \lfloor b/m \rfloor m + p,c = \lfloor c/m \rfloor m + q,d = \lfloor d/m \rfloor m + q$。
那么$a \pm c = \lfloor a/m \rfloor m + p \pm (\lfloor c/m \rfloor m + q) = (\lfloor a/m \pm c/m \rfloor) + (p \pm q)$，
同理可得$b \pm d = (\lfloor b/m \pm d/m \rfloor) + (p \pm q)$
因为$(a \pm c)\%m = (b \pm d)\%m = p \pm q$，所以$a \pm c\equiv b\pm d(mod\quad m)$。

同余式相乘的证明
设$a \% m = b \% m = p$，$c \% m = d \% m = q$，
则有$a = \lfloor a/m \rfloor m + p,b = \lfloor b/m \rfloor m + p,c = \lfloor c/m \rfloor m + q,d = \lfloor d/m \rfloor m + q$。
那么$a\times c = (\lfloor a/m \rfloor m + p ) \times (\lfloor c/m \rfloor m + q)= \lfloor a/m \rfloor \lfloor c/m \rfloor m^2 + (\lfloor a/m \rfloor q + \lfloor c/m \rfloor p)m + pq$，
同理可得$b\times d = (\lfloor b/m \rfloor m + p ) \times (\lfloor d/m \rfloor m + q)= \lfloor b/m \rfloor \lfloor d/m \rfloor m^2 + (\lfloor b/m \rfloor q + \lfloor d/m \rfloor p)m + pq$。
因为$(a \times b)\% m = pq = (b \times d)\% m$，所以$a\times c \equiv b\times d(mod\quad m)$
我们注意到$(a\%p) \times (c\%p) = pq$，那么有$(a\%p)\times (c\%p) =( a\times c)\%p$

幂运算的证明
可以由同余式相乘推出。
具体而言令$c = a,d = b$,即可得到$a^2 \equiv b^2(mod \quad m)$，
利用上一步得到的结果，再令$c = a^2,d = b^2$,即可得到$a^3 \equiv b^3(mod \quad m)$，
$\qquad \qquad \qquad \qquad \qquad \vdots$
以此类推，便可以证明$a^{n} \equiv b^{n}(mod\quad m)$。

同余相关定理(或者说同余的应用)

1. 欧拉定理
2. 费马小定理，用于求解乘法逆元
3. 中国剩余定理(也称孙子定理)
   链接如下：https://www.acwing.com/blog/content/22048/

快速幂

问题：给定一组数据$a,b,p$，求出$a^b \; mod \; p$的值

乍一看，很简单啊，写个循环不就完事了嘛！

long long res = 1;
for(int i = 0;i < b; ++ i){
    res = res * a;
}
res = res % p;

以上代码有两个问题，第一个问题是$a$可能达到$2\times 10^9$，那么$a\times a$是会爆int甚至long long类型的，第二个问题是如果给定$n$组数据，而且$n = 100000$，那么上述解法的时间复杂度就会很高，最后导致TLE。

解决办法

针对第一个问题，我们利用上面介绍的同余性质来解决。
具体而言，$a^b \; mod \; p = (a \times a^{b-1})\; mod \; p = (a\; mod \; p)(a^{b-1}\; mod \; p)$，这个等式在前面已经证明过了。因此，我们可以在写代码的过程中随时模$p$。

针对第二个问题，我们利用二进制优化该算法。
具体而言，就是将b用二进制数来表示，即$b = 0001\cdots100$，进一步表示为2的指数形式，即$b = 2^n + \dots + 2^2$，那么$a^b = a^{2^n} \times \cdots \times a^{2^2}$，因此我们只需要有限个求解$a$的幂次即可，该幂次对应于$b$的二进制表示中不等于0对应的位数。

快速幂算法
需要预处理$a^{2^0},a^{2^1},\cdots,a^{2^n}$，其中，$a^{2^1} = a^{2^0} \times a^{2^0},\cdots,a^{2^n} = a^{2^{n-1}} \times a^{2^{n-1}}$，因此快速幂算法又称为平方求幂算法。
上述预处理操作需要在$b$完成位运算(&)后进行。
具体代码如下：

long long quick_power(int a,int b,int p){
    long long res = 1;
    while(b){
        if(b & 1) res = res * a % p;//当前位为1
        a = (long long)a * a % p;
        b >>= 1;
    }
    return res;
}

当然了，还有其他求解快速幂的算法，比如利用递归+二分来求解，这里就不作介绍了。