乘法逆元

前置

快速幂

递归版

// a 的 b 次方在模 p 意义下的结果
int quick_pow(int a, int b, int p)
{
    if (b == 0)
        return 1;
    int x = quick_pow(a, b / 2, p);
    if (b % 2 == 0)
        return x * x % p;
    return x * x % p * a % p;
}

非递归版

// a 的 b 次方在模 p 意义下的结果
int quick_pow(int a, int b, int p)
{
    int res = 1;
    while (b > 0)
    {
        if (b % 2 == 1)
            res = res * a % p;
        b /= 2;
        a = a * a % p;
    }
    return res;
}

扩展欧几里得算法

累赘但好懂的写法

// 返回 ax+by=gcd(a,b) 的解 <x,y>
pair<int, int> exGCD(int a, int b)
{
    // ax+0y=a
    if (b == 0)
        return {1, 0};
    pair<int, int> nxt = exGCD(b, a % b);
    int xx = nxt.first;
    int yy = nxt.second;
    int x = yy;
    int y = xx - a / b * yy;
    return {x, y};
}

简化一点的写法

// 返回 ax+by=gcd(a,b) 的解 <x,y>
pair<int, int> exGCD(int a, int b)
{
    // ax+0y=a
    if (b == 0)
        return {1, 0};
    pair<int, int> nxt = exGCD(b, a % b);
    return {nxt.second,
            nxt.first - a / b * nxt.second};
}

常见的写法

返回 gcd，引用类型的参数传递解

int exGcd(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    int xx, yy;
    int gcd = exGcd(b, a % b, xx, yy);
    x = yy;
    y = xx - (a / b) * yy;
    return gcd;
}

费马小定理求逆元

// a 在模 p（质数） 意义下的逆元
int inv(int a, int p)
{
    return quick_pow(a, p - 2, p);
}

扩欧求逆元

// a 在模 b 意义下的逆元（gcd(a,b)==1）
int inv(int a, int b)
{
    pair<int, int> ans = exGCD(a, b);
    // a * ans.first + b * ans.second = 1
    // a * ans.first === 1 (%b)
    return (ans.first % b + b) % b;
}

线性求逆元

[math]\displaystyle{ p = \lfloor\frac{p}{i}\rfloor\times i+(p \bmod i) }[/math]

在 [math]\displaystyle{ \bmod p }[/math] 的意义下

[math]\displaystyle{ 0 \equiv \lfloor\frac{p}{i}\rfloor\times i+(p \bmod i) }[/math]

两边同时乘以 [math]\displaystyle{ i^{-1} }[/math]

[math]\displaystyle{ 0 \equiv \lfloor\frac{p}{i}\rfloor+(p \bmod i)\times i^{-1} }[/math]

两边同时乘以 [math]\displaystyle{ (p \bmod i)^{-1} }[/math]

[math]\displaystyle{ 0 \equiv \lfloor\frac{p}{i}\rfloor\times (p \bmod i)^{-1} +i^{-1} }[/math]

所以

[math]\displaystyle{ i^{-1} \equiv -\lfloor\frac{p}{i}\rfloor\times (p \bmod i)^{-1} }[/math]

inv[1] = 1;
for (int i = 2; i <= n; i++)
    inv[i] = (p - p / i) * inv[p % i] % p;

阶乘的逆元

[math]\displaystyle{ (i!)^{-1}=1^{-1}\times 2^{-1} \times \dots\times i^{-1} }[/math]

// 预处理1~n的逆元
inv[1] = 1;
for (int i = 2; i <= n; i++)
    inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
// 预处理1~n的阶乘的逆元
// invFact[i] = inv[1]*inv[2]*...*inv[i]=invFact[i-1]*inv[i]
invFact[0] = invFact[1] = 1;
for (int i = 2; i <= n; i++)
    invFact[i] = invFact[i - 1] * inv[i] % MOD;