乘法逆元

关于乘法逆元

对于两个数a,p若gcd(a,p)=1则一定存在另一个数b，使得ab ≡ 1( modp )，并称此时的b为a关于1模p的乘法逆元。我们记此时的b为inv(a)或 a -1

举个例子：

5×3 ≡ 1( mod14 ) 我们称此时的3为5关于1模14的乘法逆元。

费马小定理

假如p是质数，且gcd(a,p) = 1,那么 a^(p-1) ≡ 1 (mod p)。即：假如a是整数，p是质数，那么a的(p-1)次方除以p的余数恒等于1.

然后结合逆元的定义，就可以得到 a × a^(p-2) ≡ 1 (mod p)也就是说 a的p-2次方就是a的逆元。

typedef long long ll;
const int mod=1e9+7;
ll qpow(ll a,ll b)
{
    if(b<0) return 0;
    ll ans=1;
    a%=mod;
    while(b)
    {
        if(b&1) ans=(ans*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return ans;
}
ll inv(ll a)
{
    return qpow(a,mod-2);
}

扩展欧几里得

ax+by=1

a和p互质 (gcd = 1)

void exgcd(int a, int p, int &x, int &y) 
{
    if(0 == p){
        x = 1, y = 0;
        return ;
    }
    exgcd(p, a%p, x, y);
    int flag = x;
    x = y;
    y = flag - a/p * y;
}