数论 - 递推求逆元
递推求逆元的推导
设 ，那么有：
两边同乘 ：
带回：
易知递推边界：
代码模板
1
2
3
4
5
6
const int MOD = 1E9+7;
int Inv[100000];
void getInv(int c) {
Inv[1] = 1;
for(int i=2;i<=c;i++) Inv[i] = ((MOD - MOD/i) * Inv[MOD % i]) % MOD;
}
设 ，那么有：
两边同乘 ：
带回：
易知递推边界：
1
2
3
4
5
6
const int MOD = 1E9+7;
int Inv[100000];
void getInv(int c) {
Inv[1] = 1;
for(int i=2;i<=c;i++) Inv[i] = ((MOD - MOD/i) * Inv[MOD % i]) % MOD;
}