假设模数为p, p = i ⋅ k + r , k , r ∈ Z , 0 ≤ r < i p=i\cdot k+r,k,r\in \Z,0\leq rp=i⋅k+r,k,r∈Z,0≤r<i
两边同时对p取mod得: 0 ≡ i ⋅ k + r ( m o d p ) 0\equiv i\cdot k+r\pmod p 0≡i⋅k+r(modp)
两边同时乘 i − 1 ⋅ r − 1 i^{-1}\cdot r^{-1} i−1⋅r−1,把 i − 1 i^{-1} i−1分离出来 得: 0 ≡ k ⋅ r − 1 + i − 1 ( m o d p ) 0\equiv k\cdot r^{-1}+i^{-1}\pmod p 0≡k⋅r−1+i−1(modp)
进而 i − 1 ≡ − k ⋅ r − 1 ( m o d p ) i^{-1}\equiv -k\cdot r^{-1}\pmod p i−1≡−k⋅r−1(modp)
回到 p = i ⋅ k + r p=i\cdot k+r p=i⋅k+r, 可以推出 k = ⌊ p / i ⌋ , r − 1 = ( p % i ) − 1 k=\lfloor p/i \rfloor, r^{-1}=(p\%i)^{-1} k=⌊p/i⌋,r−1=(p%i)−1
代入即可: i − 1 ≡ − ⌊ p / i ⌋ ⋅ ( p % i ) − 1 ( m o d p ) i^{-1}\equiv -\lfloor p/i \rfloor\cdot (p\%i)^{-1}\pmod p i−1≡−⌊p/i⌋⋅(p%i)−1(modp)
写成代码一句话
inv[i]=-MOD/i*inv[MOD%i];
inv[i]=(MOD-MOD/i)*inv[MOD%i];//更好
预处理inv[0]=inv[1]=1就完工.
经典中的经典，如果
(
a
,
m
)
=
1
(a,m)=1
(a,m)=1
a
m
≡
a
(
m
o
d
m
)
a
−
1
=
a
m
−
2
设
x
=
a
−
1
x=a^{-1}
x=a−1，
a
x
≡
1
(
m
o
d
m
)
ax \equiv 1 \pmod m
ax≡1(modm)
等价于
a
x
+
m
y
=
1
ax + my = 1
ax+my=1
这样一个exgcd能解决的问题。
实际情况下:
exgcd(a,p,x,y);
x=(x%m+m)%m;
注意乘的是 i + 1 i+1 i+1
fac[0]=1;for(int i=1;i<=N;i++) fac[i]=fac[i-1]*i%MOD;
ifac[N]=qmod(fac[N], MOD-2);
for(int i=N-1;i>=0;i--) ifac[i]=ifac[i+1]*(i+1)%MOD;