查看“︁06-数学相关/04-乘法逆元”︁的源代码


== 前置：快速幂 ==

=== 非递归版 ===

<syntaxhighlight lang="cpp">
// 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;
}
</syntaxhighlight>

=== 递归版 ===

<syntaxhighlight lang="cpp">
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;
}
</syntaxhighlight>

== 费马小定理求逆元 ==

当 <math>p</math> 是质数时：

<math>a^{-1}\equiv a^{p-2}\pmod p</math>

<syntaxhighlight lang="cpp">
// a 在模 p（质数）意义下的逆元
int inv(int a, int p)
{
    return quick_pow(a, p - 2, p);
}
</syntaxhighlight>

== 扩展欧几里得求逆元 ==

当 <math>\gcd(a,b)=1</math> 时：

<syntaxhighlight lang="cpp">
// 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;
}
</syntaxhighlight>

== 线性求逆元 ==

<math>O(n)</math> 预处理 <math>1\sim n</math> 在模质数 <math>p</math> 下的逆元。

<math>i^{-1}\equiv -\lfloor\frac{p}{i}\rfloor\times (p\bmod i)^{-1}\pmod p</math>

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

== 阶乘的逆元 ==

<syntaxhighlight lang="cpp">
// 预处理 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;
</syntaxhighlight>

== 常用写法总结 ==

{| class="wikitable"
! 方法 !! 条件 !! 复杂度
|-
| 费马小定理
| <math>p</math> 是质数
| <math>O(\log p)</math>
|-
| 扩欧
| <math>\gcd(a,p)=1</math>
| <math>O(\log a)</math>
|-
| 线性递推
| <math>p</math> 是质数，求 <math>1\sim n</math>
| <math>O(n)</math>
|}


[[Category:数学相关]]
[[Category:三三文档]]