逆元

1 https://www.cnblogs.com/linyujun/p/5194184.html

a和p互质，a才有关于p的逆元

 1 //费马小定理(mod一定为质数)
 2 ll poww(ll a,ll b,ll mod){
 3     ll ans=1;
 4     a%=mod;
 5     while(b)
 6     {
 7         if(b&1) ans=(ans*a)%mod;
 8         b>>=1;
 9         a=(a*a)%mod;
10     }
11     return  ans%mod;
12 }
13 ll inv(ll a,ll mod)
14 {
15     return poww(a,mod-2,mod);
16 }
17 //扩展欧几里得
18

typedef long long LL;
void ex_gcd(LL a, LL b, LL &x, LL &y, LL &d){
if (!b) {d = a, x = 1, y = 0;}
else{
ex_gcd(b, a % b, y, x, d);
y -= x * (a / b);
}
}
LL inv(LL t, LL p){//如果不存在，返回-1
LL d, x, y;
ex_gcd(t, p, x, y, d);
return d == 1 ? (x % p + p) % p : -1;
}

这个方法不限于求单个逆元，比前两个好，它可以在O(n)的复杂度内算出n个数的逆元

递归就是上面的写法，加一个记忆性递归，就可以了

递推这么写



#include<cstdio>
const int N = 200000 + 5;
const int MOD = (int)1e9 + 7;
int inv[N];
int init(){
    inv[1] = 1;
    for(int i = 2; i < N; i ++){
        inv[i] = (MOD - MOD / i) * 1ll * inv[MOD % i] % MOD;
    }
}
int main(){
    init();
}