乘法逆元：修订间差异
跳转到导航
跳转到搜索
创建页面，内容为“==前置== ===快速幂=== ====递归版==== <syntaxhighlight lang="cpp" line> // 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; } </syntaxhighlight> ====非递归版==== <syntaxhighlight lang="cpp" line> // a 的 b 次方在模 p 意义下的结果 int quick_pow(int a, int b, int…” |
无编辑摘要 |
||
| 第45行： | 第45行： | ||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
[[分类:代码模板]] | |||
2026年2月6日 (五) 02:19的版本
前置
快速幂
递归版
// 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;
}
费马小定理求逆元
// a 在模 p（质数） 意义下的逆元
int inv(int a, int p)
{
return quick_pow(a, p - 2, p);
}