快速幂与快速乘小结

题目链接：牛客网小白月赛12-B题

题目描述：

链接：https://ac.nowcoder.com/acm/contest/392/B
来源：牛客网
找到了心仪的小姐姐月月后，华华很高兴的和她聊着天。然而月月的作业很多，不能继续陪华华聊天了。华华为了尽快和月月继续聊天，就提出帮她做一部分作业。
月月的其中一项作业是：给定正整数A、B、P，求$A^{B}modP$ABmodP的值。华华觉得这实在是毫无意义，所以决定写一个程序来做。但是华华并不会写程序，所以这个任务就交给你了。
因为月月的作业很多，所以有T组询问。
输入描述:
第一行一个正整数T表示测试数据组数。
接下来T行，每行三个正整数A、B、P，含义如上文。
输出描述:
输出T行，每行一个非负整数表示答案。
示例1
输入
2
2 5 10
57284938291657 827493857294857 384729583748273
输出
2
18924650048745

快速幂:

此题同时用到了快速幂和快速乘，所以在此总结一下；

首先是快速幂是用于快速求解$A^{B}modP$ABmodP这类问题
对于 $A^{B}modP$ABmodP 这类问题，朴素的做法是

int tmp = 1;
for(int i = 0; i < B; i++)
    tmp = (tmp * A) % MOD;

按照题意要求模拟$A^{B}$AB过程中每次取余即可；这样做，虽然结果是对的，但是效率不够高.时间复杂度为O(B);
那这个过程能不能加速呢？ 是可以的，就是我们今天要说的这个快速幂；
那他的原理是咋样的呢？
如果B是偶数 那么有 $A^{B}modP$ABmodP 等价于 $A^{2^{\frac{B}{2}}}modP$A22B​modP
如果B是奇数 那么有 $A^{B}modP$ABmodP 等价于 $A * A^{2^{\frac{B-1}{2}}}modP$A∗A22B−1​modP
举个例子
$3^{5}mod4$35mod4
第一步:
初始化最终结果tmp = 1
我们发现5是奇数 所以可以将其拆分为 $3 \times 3^{2^{\frac{5-1}{2}}}modP$3×3225−1​modP
显然 我们可以计算出
tmp = tmp $\times$× A, A = A $\times$× A
然后对B进行右移操作，即除以2然后向下取整，此时
A = 9, B = 2, tmp = 3,对剩下的部分继续快速幂
第二步:
我们发现没算的那个2是偶数 所以可以得出 $3^{2^{\frac{2}{2}}}modP$3222​modP
显然 我们可以计算出 A = A $\times$× A,然后对B进行右移操作，即除以2然后向下取整，此时A = 81, B = 1, tmp = 3,对剩下的部分继续快速幂
第三步:
我们发现没算的那个1是奇数 所以可以得出 $3^{2^{\frac{1-1}{2}}}modP$3221−1​modP
显然 我们可以计算出 tmp = tmp $\times$× A, A = A $\times$× A
然后对B进行右移操作，即除以2然后向下取整，此时A = 729, B = 0, tmp = 243;

第四步:
此时B为0，我们终止循环，返回tmp % mod即可；
显然，我们只是当B为奇数时把结果乘到tmp中，B为偶数时，我们只将A改变为其的平方即可；这样就可以加速运算；
我自己的pow_mod

#define long long long
long pow_mod(long a, long b, long mod)
{
    long tmp = 1;
    while(b)
    {
        if(b & 1)
            tmp = ( (tmp % mod) * (a % mod) ) % mod;
        a = ( (a % mod) * (a % mod) ) % mod;
        b >>= 1;
    }
    return tmp;
}

快速乘

考虑到在做快速幂的时候 a $\times$× a可能会爆long long. 如果你说你要用Java或Python的大整数，那也可以，不过还是建议学一下快速乘；
举个例子:
20 $\times$× 11=20 $\times$× (1011)=20 $\times$× $2^{3}$23 $\times$× 1 + 20 $\times$× $2^{2}$22 $\times$× 0 + 20 $\times$× $2^{1}$21 $\times$× 1 + 20 $\times$× $2^{0}$20 $\times$× 1 = 160 + 40 + 20 = 220
我们可以看到，每次可以给a乘以2，若当前位为1则代表有贡献，对答案进行更新，否则就是没有贡献，跳过即可；这样我们每次做的都是 + 操作，所以不必担心爆long long；时间复杂度是O(logb)

#define long long long
long mul(long a, long b, long mod)
{
    long tmp = 0;
    while(b)
    {
        if(b & 1)
            tmp = (tmp + a) % mod;
        a = (a + a) % mod;
        b >>= 1;
    }
    return tmp % mod;
}

题目代码:

#include <bits/stdc++.h>
using namespace std;

#define long long long
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define MAX_N 200010

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

long pow_mod(long a, long b, long mod)
{
    long tmp = 1;
    while(b)
    {
        if(b & 1)
            tmp = mul(tmp, a, mod);
        a = mul(a, a, mod);
        b >>= 1;
    }
    return tmp;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while(t--)
    {
        long a, b, mod;
        cin >> a >> b >> mod;
        cout << pow_mod(a, b, mod) << endl;
    }

    return 0;
}