数学（二）

快速幂

1.快速幂求xᵇ % p

其中x,b,p均∈ [1,1e9],时间复杂度为O(logb)

算法原理：反复平方法‬

b=2ˣ¹＋. . . . . .＋2ˣⁿ (通过2进制数位实现)，比如11的二进制为1011，1011中第零位为1，代表 2⁰ ，第一位为1，代表 2¹ ，第二位为0，代表0，第三位为1，代表 2³ ，所以11=2^0+2^1+2^3。同理， xᵇ＝x²⁰×. . . . . .x²ˡᵒᵍᵇ 可快速得到。其中 x²ⁿ 通过反复平方得到。

参考代码：

LL qmi(int x, int b, int p)

{

LL res = 1 % p;

while (b)

{

if (b & 1) res = res * x % p;

x = x * (LL)x % p;

b ＞＞= 1;

}

return res;

}

2.快速幂求x mod p的乘法逆元‬

初等数学上乘法逆元就是倒数（a*x=1，则x是a的乘法逆元），算法中我们常讨论取模运算的乘法逆元（α * xmodp ≡ 1 ，代码表示为a * x % p = 1，x是a%p的乘法逆元）

算法中常求乘法逆元将除法变成乘法以简化运算。

当n为质数时，可以用快速幂求逆元：

代码与快速幂代码相同，只不过参数改为qmi（x,p-2,p）【推导用到了费马小定理】

龟速乘

与快速幂类似，求(α * b)modp的值，a，b，p范围均[1,1e18]。

其实就是把快速幂的相乘算法改为相加算法

LL qadd(LL a, LL b, LL p)

{

LL res = 0;

while (b)

{

if (b & 1) res = (res + a) % p;

a = (a + a) % p;

b ＞＞= 1;

}

return res;

}

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。