数论 - 递推求逆元

2016/10/31

递推求逆元的推导

,那么有:

两边同乘

带回:

易知递推边界:

代码模板

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;
}