算法學習（三）——逆元

當運算時需要求模的時候，可以直接做的有+-*但是不滿足/

而逆元就是通過某種運算來達到求(a/b)%p的結果

當b*c≡1(mod p)時，

有(a/b)%p=(a/b*b*c)%p=(a*c)%p

這裡c就是b關于p的逆元 

那麼如何求c呢

費馬小定理

 當p為素數時，有 a^p≡a(mod p)

故有a^p≡1(mod p)

是以a關于p的逆元就是a^(p-2)

這個幂可以使用快速幂來得出

擴充歐幾裡得算法

對于不完全為0的非負整數a,b，必存在整數x,y，滿足ax+by=gcd(a,b)

是以，求a*x≡1(mod p)

即求a*x+p*y=1=gcd(a,b)/gcd(a,b)

也就是先求出a*x+p*y=gcd(a,b)

然後x=x/gcd(a,b)即可

注意：x可能為負的，需要x=x+p

typedef long long ll;

ll exgcd(ll a, ll b, ll &x, ll &y)    //這是擴充歐幾裡得
{
    if(b == 0){
        x = 1;
        y = 0;
        return a;
    }
    ll t = exgcd(b, a%b, x, y);
    ll tmp = y;
    y = x - a / b * y;
    x = tmp;
    return t;
}

k = exgcd(k ,p ,x ,i);
if(x < 0) x += p;                     //防止x為負
x = x / k;