數論求逆元的三種方法

擴充歐幾裡德算法

//非遞歸的擴充歐幾裡德算法  
//傳回a、b的gcd，同時x、y滿足ax+by=gcd  
int_t exEuclid(int_t a,int_t b,int_t&x,int_t&y){  
    int_t x0 = 1, y0 = 0;  
    int_t x1 = 0, y1 = 1;  
    x = 0; y = 1;  
    int_t r = a % b;  
    int_t q = ( a - r ) / b;  
    while( r ){  
        x = x0 - q * x1;  
        y = y0 - q * y1;  
        x0 = x1; y0 = y1;  
        x1 = x; y1 = y;  
        a = b; b = r; r = a % b;  
        q = ( a - r ) / b;  
    }  
    return b;  
}  
//求a相對于p的逆元，a、p互質才存在逆元  
int_t inv(int_t a,int_t p){  
    int_t x,y;  
    int_t r = exEuclid(a,p,x,y);  
    if ( r != 1 ) return 0;  
    x = x % p;  
    if ( x < 0 ) x += p;  
    return x;  
}  
           

費馬小定理

//計算a^b%mod
llt powerMod(llt a,llt b,llt mod){
    llt ret = 1LL;
    a %= mod;
    while( b ){
        if ( b & 1LL ) ret = (ret*a)%mod,--b;
        b >>= 1LL;
        a = multiMod(a,a,mod);
    }
    return ret;
}
llt inv( int x ,int mod ){
    return powerMod( x, mod-2 ,mod );
}



           

線性篩逆元

這個做法實際上是這樣的，首先  1−1≡1(modp) 1−1≡1(modp)

然後我們設  p=k⋅i+r, r<i, 1<i<p p=k⋅i+r, r<i, 1<i<p

再将這個式子放到 modp modp 意義下就會得到

k⋅i+r≡0(modp) k⋅i+r≡0(modp)

兩邊同時乘上  i−1⋅r−1 i−1⋅r−1 就會得到

k⋅r−1+i−1i−1i−1≡≡≡0−k⋅r−1−⌊pi⌋⋅(pmodi)−1(modp)(modp)(modp)  k⋅r−1+i−1≡0(modp)i−1≡−k⋅r−1(modp)i−1≡−⌊pi⌋⋅(pmodi)−1(modp) 

于是就可以從前面推出目前的逆元了，代碼也就一行

int const  Ns = 3e4+7;
llt inv[Ns]={0,1};
void init(){
    for (int i = 2;i <= Ns;++i ){
        inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;
    }
}
           

參考 http://blog.miskcoo.com/2014/09/linear-find-all-invert