数学：快速幂、费马小定理、乘法逆元

Bellala · 2024-06-19 10:07:10 · 算法·理论

1. 快速幂、龟速乘、快速乘

快速幂：O(\log b) 求 a^b\pmod {m}

const int mod = 1e9 + 7; //模数最好写成常数
int qpow(int a, int b) { //求a^b%mod，其中b>=0，mod>1
    int s = 1;
    while (b > 0) {
        if (b & 1) s = 1ll * s * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return s;
}

龟速乘：O(\log b) 求 a\cdot b\pmod m

int qmul(int a, int b) {
    int s = 0;
    while (b > 0) {
        if (b & 1) s = (s + a) % mod;
        a = (a + a) % mod;
        b >>= 1;
    }
    return s;
}

快速乘：用浮点数求 a\cdot b\pmod m

2009国家集训队论文《论程序底层优化的一些方法与技巧》骆可强

https://img-blog.csdn.net/20181015235114249?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5YW5fcm9zZQ

其他：int128

快速幂例题：https://www.luogu.com.cn/problem/U400677

2. 费马小定理

若 p 为质数，a 与 p 互质，则 a^{p-1} \equiv 1 \pmod p

证明：

考虑序列 1, 2, 3, \cdots, p-1，取一个不为 p 倍数的数 a

考虑 a,2a,3a,\cdots ,(p-1)a 对 p 的余数，这些数是原序列的重新排列（例子：a=5,p=7，得到 5,3,1,6,4,2）

所以 a \cdot 2a \cdot 3a \cdot ... \cdot (p-1)a = 1 \cdot 2 \cdot 3 \cdot ... \cdot (p-1) \pmod p

所以 a^{p-1} \equiv 1 \pmod p

3. 乘法逆元

若 ax\equiv 1\pmod m，则称 x 为 a 在模 m 意义下的乘法逆元，记作 a^{-1} 举例：3 * 2 % 5 = 1

逆元存在的条件：a 与 m 互质。可用裴蜀定理理解

求逆元的方法：

(1) 快速幂+费马小定理求逆元（模数是质数）

举例：$3^{5-2}\%5=2

(2) exgcd求解线性同余方程（不要求模数m是质数，只要求a与m互质）

解方程 ax+my=1

(3) 递推求逆元（模数是质数）（不太好用）

求 a^{-1}\pmod p

推导：记 k = \lfloor p/a\rfloor,r=p\% a，则 p = ka+r。那么 ka+r\equiv 0\pmod p，解得 a^{-1}\equiv -kr^{-1}\pmod p

用这种方法可以递归 O(\log p) 求一个数的逆元，或 O(p) 求 1\sim p-1 的逆元

// 求1~p-1的逆元
inv[1] = 1;
for (int i = 2; i < p; ++i) //防止负数
    inv[i] = (p - p / i) * inv[p % i] % p;

(4) 线性求 1!\sim n! 的逆元

相邻两项的逆元有什么关系？

(n!)^{-1} = (n+1)^{-1}\cdot (n+1)

// 求0~n的阶乘
fact[0] = 1;
for (int i = 1; i <= n; ++i)
    fact[i] = fact[i - 1] * i % p;
// 费马小定理求n!的逆元
factinv[n] = qpow(fact[n], p - 2);
// 求(n-1)!~0!的逆元
for (int i = n - 1; ~i; --i)
    factinv[i] = factinv[i + 1] * (i + 1) % p;

求得 1!\sim n! 的逆元后，也可以这样求 1\sim n 的逆元：n=(n!)^{-1}\cdot (n-1)!