快速幂|取模 FastPowMod | 倚栏听风—

在处理一些数论题目的时候，我们经常有的时候会遇到一些高指数的问题，就比如在判断素数的时候所使用的ML素性判定（传送门待完善）

快速取幂的原理其实并不复杂，我们以pow(2,10)为例

一般的计算就是

$$2*2*2*2*2*2*2*2*2*2=1024$$

另一种就是使用了分治法的思想

$$2*2*2*2*2*2*2*2*2*2=4*4*4*4*4=4*16*16=64*16=1024$$

而使用了二进制方式的快速幂则更为巧妙

将10转换为二进制以后可以得到

0000 0000 0000 0000 0000 0000 0000 1010

我们可以发现$ pow（2,10) $其实可以体现出来是 $ pow(2,8)*pow(2,2) $ ，对应到数位中也就是第二位和第四位，也就是说我们只需要在二进制位为1处进行一次乘的操作即可

而取余的性质则如下

$$(a + b) \% p = (a \% p + b \% p) \% p $$

$$(a - b) \% p = (a \% p - b \% p) \% p $$

$$(a * b) \% p = (a \% p * b \% p) \% p $$

$$(a ^ b) \% p = ((a \% p)^b) \% p $$

在快速幂的模板中稍加更改就可以实现在每一步操作中取余的目的

模板如下

/*
 * @Author: Gehrychiang
 * @LastEditors  : Please set LastEditors
 * @Website: www.yilantingfeng.site
 * @E-mail: gehrychiang@aliyun.com
 */
#include <bits/stdc++.h>
using namespace std;

long long fastMul(long long a, long long b, long long mod)
{
    long long res = 0;
    while (b)
    {
        if (b & 1)
        {
            res = (res + a) % mod;
        }
        a = (a + a) % mod;
        b >>= 1;
    }
    return res;
}

long long fastPowMod(long long a, long long n, long long mod)
//long long fastPow(long long a, long long n)
{
    if (n == 0 && a != 0)
        return 1;
    if (n != 0 && a == 0)
        return 0;
    long long base = a;
    long long res = 1;
    while (n)
    {
        if (n & 1)
        {
            res = fastMul(res, base, mod);
            //res*=base;
        }
        base = fastMul(base, base, mod);
        //base*=base;
        n >>= 1;
    }
    return res % mod;
    //return res;
}
int main()
{
    long long b, q, k;
    while (cin >> b >> q >> k)
    {
        long long ans = fastPowMod(b, q, k);
        printf("%lld\n",ans);
    }
    return 0;
}

Update:

更新了使用快速乘的模板，可以有效防止在唯一的一步乘法运算中溢出long long范围

快速幂||取模 FastPowMod