06-数学相关/04-乘法逆元

前置：快速幂

非递归版

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

递归版

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 1LL * x * x % p;
    return 1LL * x * x % p * a % p;
}

费马小定理求逆元

当 [math]\displaystyle{ p }[/math] 是质数时：

[math]\displaystyle{ a^{-1}\equiv a^{p-2}\pmod p }[/math]

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

扩展欧几里得求逆元

当 [math]\displaystyle{ \gcd(a,b)=1 }[/math] 时：

// a 在模 b 意义下的逆元（要求 gcd(a,b)==1）
int inv(int a, int b)
{
    auto [x, y] = exGCD(a, b);
    // a*x + b*y = 1，所以 a*x === 1 (%b)
    return (x % b + b) % b;
}

线性求逆元

[math]\displaystyle{ O(n) }[/math] 预处理 [math]\displaystyle{ 1\sim n }[/math] 在模质数 [math]\displaystyle{ p }[/math] 下的逆元。

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

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

阶乘的逆元

// 预处理 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;

常用写法总结

方法	条件	复杂度
费马小定理	[math]\displaystyle{ p }[/math] 是质数	[math]\displaystyle{ O(\log p) }[/math]
扩欧	[math]\displaystyle{ \gcd(a,p)=1 }[/math]	[math]\displaystyle{ O(\log a) }[/math]
线性递推	[math]\displaystyle{ p }[/math] 是质数，求 [math]\displaystyle{ 1\sim n }[/math]	[math]\displaystyle{ O(n) }[/math]