【ybt高效进阶6-3-3】线性求逆元（数学）

线性求逆元

题目链接：ybt高效进阶6-3-3

题目大意

给你 n,p，要你求 1~n 每个数在模 p 意义下的逆元。

思路

线性求逆元的公式就是：

i n v i = ( ( p − p / i ∗ i n v p   m o d   i )   m o d   p + p )   m o d   p inv_i=((p-p/i*inv_{p\bmod i})\bmod p+p)\bmod p invi​=((p−p/i∗invpmodi​)modp+p)modp

这里给一下证明：

因为是线性，所以假设我们求 i i i，那 1 ∼ i − 1 1\sim i-1 1∼i−1 的我们都求出来了。

那 p p p 可以表示成 ⌊ p i ⌋ ∗ i + r ( 0 ⩽ r < i ) \left\lfloor\dfrac{p}{i}\right\rfloor*i+r(0\leqslant r<i) ⌊ip​⌋∗i+r(0⩽r<i)，所以就有

⌊ p i ⌋ ∗ i + r ≡ 0 (   m o d     p ) \left\lfloor\dfrac{p}{i}\right\rfloor*i+r\equiv0(\bmod\ p) ⌊ip​⌋∗i+r≡0(mod p)

然后两边都乘 i n v i ∗ i n v r inv_i*inv_r invi​∗invr​，就有 ⌊ p i ⌋ ∗ i n v r + i n v i ≡ 0 (   m o d     p ) \left\lfloor\dfrac{p}{i}\right\rfloor*inv_r+inv_i\equiv0(\bmod\ p) ⌊ip​⌋∗invr​+invi​≡0(mod p)

i n v i ≡ − ⌊ p i ⌋ ∗ i n v r (   m o d     p ) inv_i\equiv-\left\lfloor\dfrac{p}{i}\right\rfloor*inv_r(\bmod\ p) invi​≡−⌊ip​⌋∗invr​(mod p)

然后由于 ( 0 ⩽ r < i ) (0\leqslant r<i) (0⩽r<i)， i n v r inv_r invr​ 是已知的，所以就得出了 i n v i inv_i invi​。

代码

#include<cstdio>

using namespace std;

int n, p, inv[3000001];

int main() {
	scanf("%d %d", &n, &p);
	
	inv[1] = 1;
	for (int i = 2; i <= n; i++)//不开 long long 见祖宗
		inv[i] = ((1ll * p - 1ll * p / i * inv[p % i]) % p + p) % p;
	
	for (int i = 1; i <= n; i++) printf("%d\n", inv[i]);
	
	return 0;
}