求逆元的几种办法

资料来源：https://blog.csdn.net/danliwoo/article/details/52015917

 

题目：http://codeforces.com/contest/697/problem/E

一般求法

求a关于N的逆元，即要解同余方程ax≡1(modN)ax≡1(modN)的解x. 
ax≡1(modN)⇔ax+Ny=1
仅当a与N互质时，存在aa的逆元，利用扩展欧几里得求解。 
这里N不一定是素数

LL extend_Euclid(LL a, LL b, LL &x, LL &y){
    if(b == 0){
        x = 1; y = 0;
        return a;
    }
    LL r = extend_Euclid(b, a%b, y, x);
    y -= a/b*x;
    return r;
}

x = (x % N + N) % N

---

费马小定理求逆元

#define LL long long
LL poo(LL a, int k, int m){
    LL res = 1;
    while(k){
        if(k & 1LL)
            res = res * a % m;
        k >>= 1;
        a = a*a%m;
    }
    return res;
}

---

CF 696C

---

int rev[N];
void get_rev(){
    rev[1] = 1;
    for(int n = 2;n < N;n++){
        int k = P % n, t = P / n;
        rev[n] = 1LL*(P-t)*rev[k]%P;
    }
}