LaTeX可敲死我了

快速幂

1.原理

• 快速幂可以用$O(logk)$的时间快速计算出$a^k (mod \ p)$
• 预处理：$a^{2^0} mod \ p$，$a^{2^1} mod \ p$，…，$a^{2^{log^k}} mod \ p$
• 如何预处理：后一个数为前一个数的平方，一共logk个数
• 拆分：$a^k = a^{2^{x_1}+2^{x_2}+…2^{x_t}}=a^{2^{x_1}} \times a^{2^{x_2}} \times…\times a^{2^{x_t}}$
• 只要判断k的二进制上对应位置上的1，然后查表累乘即可在$O(log^k)$时间之内查表获得答案

2.代码模板

//求a^k mod p
long qmi(long a, long k, long p){
    long res = 1;
    while(k != 0){
        if((k & 1) == 1) res = (res * a) % p;
        k >>= 1;
        a = a * a % p;
    }
    return res;
}

快速幂求逆元

1.逆元

• $\frac{a}{b} \equiv a \times x (mod \ m)$， 且b与m互质
• 则x称为$b(mod \ m)$的逆元，也记做$b^{-1}$

2.逆元的性质

• $\frac{a}{b} \equiv a \times b^{-1} (mod \ m)$
• $b \times \frac{a}{b} \equiv b \times a \times b^{-1} (mod \ m)$
• $a \equiv a \times b \times b^{-1} (mod \ m)$
• 所以：$b \times b^{-1} \equiv 1 (mod \ m)$

3.费马小定理

• $b^{p-1} \equiv 1 (mod \ p)$，当且仅当b，p互质
• b,p不互质，则b没有逆元
• 反之b,p互质，b必有逆元
• b的逆元为：$b \times b^{p-2} \equiv 1 (mod \ p)$
• 到这里，我们发现$b^{p-2}$可以用快速幂算法求出，即当$b$和$p$互质的时候，我们可以通过快速幂来求得$b$的逆元$b^{p-2}$

4.代码模板

//b的逆元
qmi(b, p-2, p)