逆元

· · 个人记录

逆元

费马小定理

a^p\equiv{a}\pmod{p}(p\in{Prime})

那么我们在两边同时除以a^2

a^{p-2}\equiv{a^{-1}}\pmod{p}

注意，这个方法只能求模质数意义下的逆元

int pow_(int a,int b,int p){
    int ans=1;
    while(b!=0){
        if(b&1) ans=(ans*a)%p;
        b>>=1;
        a=(a*a)%p;
    }
    return ans%p;
}
int inv(int i,int mod){
    return pow_(i,mod-2,mod);
}

扩欧(exgcd)

int exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=(a/b)*x;
    return d;
}
int inv(int i,int mod){
    int x,y;
    int d=exgcd(i,mod,x,y);
    return ((x/d)%mod+mod)%mod;
}

线性递推

int inv(int i,int mod){
    if(i==1) return 1;
    return (-(mod/i)*inv(mod%i,mod)%mod+mod)%mod;
}

数论