逆元

求逆元模板

Part 1：求逆元

拓展欧几里得求法
由 a * b=1(mod p) 得 a * b+p * y=1(mod p) 则可以用拓展欧几里得求解

void ex_gcd( int b, int p, int & a, int & k ) {  //拓展欧几里得
    if( p == 0 ) {
        a = 1; k = 0;
        return;
    }
    ex_gcd( p, b % p, k, a );
    k -= b / p * a;
    return;
}
int main() {
    int b, p;
    cin >> b >> p;
    int a, k;
    ex_gcd( b, p, a, k );
    if( a < 0 ) a += p;
    cout << a << endl;
    return 0;
}

快速幂求法（费马小定理）
由a^(p-1)=1(mod p)(费马小定理) --> a^(p-2) =a^(-1) (mod p)

int ksm(int a,int b,int p)
{
      int ans=1;
      while(b){
            if(b&1) ans=ans*a%p;
            b>>=1;
            a=a*a%p;
      }
      return ans;
}
int main() {
    int b, p;
    cin >> b >> p;
    cout<<ksm(b,p-2,p);
    return 0;
}

Part 2：求出1！，2！，3！，... n!逆元

先求n！,再利用1/(n-1)!= 1/n!*n%Mod倒推

int inv( int b, int p ) {
    int a, k;
    exPower( b, p, a, k );
    if( a < 0 ) a += p;
    return a;
}
void init( int n ) {
    Fact[ 0 ] = 1;
    for( int i = 1; i <= n; ++i ) Fact[ i ] = Fact[ i - 1 ] * i % Mod;
    INV[ n ] = inv( Fact[ n ], Mod );
    for( int i = n - 1; i >= 0; --i ) INV[ i ] = INV[ i + 1 ] * ( i + 1 ) % Mod;
    return;
}

Part 3：逆元的线性递推式

Inv[ 1 ] = 1;
for( int i = 2; i <= n; i++ )
    Inv[ i ] = ( p - p / i ) * Inv[ p % i ] % p;