预处理逆元

预处理1~n逆元

若用费马小定理+快速幂则复杂度为 $O(nlogn)$ 较慢

从$p$ 与 $i$ 的关系入手 $p = ki+r$ $(k =\lfloor\frac{p}{i} \rfloor, r = p mod i )$ $(i < p , k < p, r < i)$

则 $ki+ r \equiv 0 (mod \ p )$

同乘 $i^{-1}\times r^{-1}$

$ ki\times i^{-1}\times r^{-1} + r\times r^{-1}\times i^{-1} \equiv 0 (mod \ p )$

移项 $k =\lfloor\frac{p}{l} \rfloor , r = p\ mod \ i$ $i^{-1} \equiv -k\times r^{-1} (mod \ p )$ $i^{-1} \equiv -\lfloor\frac{p}{i}\rfloor\times (p mod \ i)^{-1} (mod \ p )$

∵ (p mod i) < i 在求出 $i^{-1}$之前已经求出，所以可以用之前的来递推

显然 $inv[i] = -\lfloor\frac{p}{i}\rfloor\times inv[p \% mod i] mod p$

因为题目在正整数范围内 [以及] 为了防爆 int , 则两边同时加 p, 并不影响原值 p mod p = 0 . $inv[i] = (long long)(p-\lfloor\frac{p}{i}\rfloor)\times inv[p \%i ] mod p$

1
2
3
4
5
6
7
8
9


const int N = 114514;
int n , p ;
int inv[N];
void gen(){
	inv[0] = 0 , inv[1] = 1;
	for(int i = 2;i<N;++i){
		inv[i] = (long long)(p - p/i)* inv[p % i] % p;
	}
}

作业

https://www.luogu.com.cn/problem/P3811