查看“︁06-数学相关/08-快速幂与快速乘”︁的源代码


== 快速幂 ==

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