33DAI：导入1个版本

2026-05-20T18:12:12Z

导入1个版本

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

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

2026-05-20T16:50:33Z

批量导入三三文档

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

33DAI：导入1个版本

2026-05-20T16:25:43Z

导入1个版本

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

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

2026-05-20T16:22:29Z

批量导入三三文档

新页面

== 快速幂 ==

计算 <math>a^b</math>（模 <math>p</math> 意义下），时间复杂度 <math>O(\log b)</math>。

=== 非递归版 ===

<syntaxhighlight lang="cpp">
int quick_pow(int a, int b, int p)
{
int res = 1;
while (b > 0)
{
if (b & 1)
res = 1LL * res * a % p;
b >>= 1;
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>a\times b</math>（模 <math>p</math> 意义下），防止 <math>a\times b</math> 爆 <code>long long</code>。

=== 使用 <code>__int128</code> ===

<syntaxhighlight lang="cpp">
long long mul(long long a, long long b, long long p)
{
return (__int128)a * b % p;
}
</syntaxhighlight>

=== 二进制拆分 ===

<syntaxhighlight lang="cpp">
long long mul(long long a, long long b, long long p)
{
long long res = 0;
while (b)
{
if (b & 1)
res = (res + a) % p;
a = (a + a) % p;
b >>= 1;
}
return res;
}
</syntaxhighlight>

=== 使用 <code>long double</code> ===

<syntaxhighlight lang="cpp">
long long mul(long long a, long long b, long long p)
{
long long t = (long double)a * b / p;
long long res = a * b - t * p;
if (res < 0)
res += p;
if (res >= p)
res -= p;
return res;
}
</syntaxhighlight>

== 矩阵快速幂 ==

见 [[05-算法模板/05-矩阵快速幂|矩阵快速幂]]。

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

06-数学相关/08-快速幂与快速乘 - 版本历史

33DAI：​导入1个版本

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

33DAI：​导入1个版本

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

33DAI：导入1个版本

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

33DAI：导入1个版本

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