逆元

发表于 更新于 分类于 本文字数： 267 阅读时长 ≈ 1 分钟

在数论中，如果,那么和在模意义下互为乘法逆元，记作

计算逆元方法

拓展欧几里得

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
long long exgcd(long long a, long long b, long long &x, long long &y)// 拓欧
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    long long d = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}
long long inv(long long a, long long p)
{
    long long x, y;
    if (exgcd(a, p, x, y) != 1) // 无解的情形
        return -1;
    return (x % p + p) % p;
}

费马小定理

若是质数，且，则有，于是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
long long qpow(long long a, long long n, long long p)// 快速幂
{
    long long ans = 1;
    while (n)
    {
        if (n & 1)
            ans = ans % p * a % p;
        a = a % p * a % p;
        n >>= 1;
    }
    return ans;
}
long long inv(long long a, long long p)
{
    return qpow(a, p - 2, p);
}

线性递推

1
2
3
4
5
6
7
8
9
10
11
12
long long Inv[MAXN] = {0, 1};
inline long long mod(long long a, long long p)
{
    return (a % p + p) % p;
}
long long inv(long long a, long long p)
{
    if (Inv[a])
        return Inv[a];
    Inv[a] = mod(-p / a * inv(p % a, p), p);
    return Inv[a];
}