启蒙

对于扩展欧几里得原理一直都是一知半解，没有实际地深入理解，最近看了龙哥的笔记，恍然大悟，赶紧mark一下。

定义：

满足b*k≡1 (mod p)的k值就是b关于p的乘法逆元。

为什么要有乘法逆元呢？

当我们要求（a/b） mod p的值，且a很大，无法直接求得a/b的值时，我们就要用到乘法逆元。
我们可以通过求b关于p的乘法逆元k，将a乘上k再模p，即(a*k) mod p。其结果与(a/b) mod p等价。

逆元 ：(a/b) (mod n) = (b x) (mod n)。
x表示b的逆元。并且 bx ≡ 1 (mod n ) 注意：只有当b与n互质的时候才存在逆元

欧几里得

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/* 
复杂度(log n),表示a关于取摸n的逆元，
要求 a，n互质
*/
//运用扩展欧几里得算法求
ll inv(ll a, ll n)
{
    ll x, y;
    extend_gcd(a, n, x, y);
    x = (x % n + n) % n;
    return x;
}
 
//扩展欧几里得算法
ll extend_gcd(ll a, ll b, ll &x, ll &y)//求解ax+by=gcd(a,b)
{
     if (b == 0) {
        x = 1, y = 0;
        return a;
     }
    else{
            ll r = extend_gcd(b, a % b, y, x); //递归求解
            y -= x * (a / b);
            return r;
    }//x=(x%b+b)%b x的最小整数解
}

费马小定理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*=========================================
    逆元 求N关于P的逆元（P为质数）
    复杂度：O（logN）
=========================================*/
const int mod = 1000000009;
long long quickpow(long long a, long long b) {
    if (b < 0) return 0;
    long long ret = 1;
    a %= mod;
    while(b) {
        if (b & 1) ret = (ret * a) % mod;
        b >>= 1;
        a = (a * a) % mod;
    }
    return ret;
}
//费马小定理求逆元（M必须是质数）
long long inv(long long a) {
    return quickpow(a, mod - 2);
}