33DAI：导入1个版本

2026-05-20T18:12:11Z

导入1个版本

←上一版本		2026年5月20日 (三) 18:12的版本
（没有差异）

->Importer：批量导入三三文档

2026-05-20T16:50:33Z

批量导入三三文档

←上一版本		2026年5月20日 (三) 16:50的版本
（没有差异）

33DAI：导入1个版本

2026-05-20T16:25:41Z

导入1个版本

←上一版本		2026年5月20日 (三) 16:25的版本
（没有差异）

->Importer：批量导入三三文档

2026-05-20T16:22:29Z

批量导入三三文档

新页面

== 前置：快速幂 ==

=== 非递归版 ===

<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:三三文档]]

06-数学相关/04-乘法逆元 - 版本历史

33DAI：​导入1个版本

->Importer：​批量导入三三文档

33DAI：​导入1个版本

->Importer：​批量导入三三文档

33DAI：导入1个版本

->Importer：批量导入三三文档

33DAI：导入1个版本

->Importer：批量导入三三文档