06-数学相关/08-快速幂与快速乘

快速幂

计算 [math]\displaystyle{ a^b }[/math]（模 [math]\displaystyle{ p }[/math] 意义下），时间复杂度 [math]\displaystyle{ O(\log b) }[/math]。

非递归版

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;
}

递归版

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;
}

快速乘

计算 [math]\displaystyle{ a\times b }[/math]（模 [math]\displaystyle{ p }[/math] 意义下），防止 [math]\displaystyle{ a\times b }[/math] 爆 long long。

使用 __int128

long long mul(long long a, long long b, long long p)
{
    return (__int128)a * b % p;
}

二进制拆分

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;
}

使用 long double

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;
}

矩阵快速幂

见 矩阵快速幂。