C++:快速幂模板

PS：链接：没有的同学请注册登录 - 沐枫OJhttps://www.mfstem.org/p/598

        输入a、b、p,输出a ^ b mod p 的值。

        数据范围（1 ≤ a、b、p ≤ 10¹⁸）

输入：2 10 9
输出：7

        乍一看，你有没有想做循环的想法

        一看数据......爆了

        那么，该怎么办呢？

        二进制......

        好像可以耶

        用二进制拆分b

        我们用ans记录答案，因为是乘法，别忘记初始化为1

        看样例吧
       10 = （1010）₂

        用while拆位

while(z > 0){
    
}

       用一个变量sum计算现在的单位，初始化为a

        如果这个二进制位是1

        ans *= sum

        ？？？

        敲黑板啦！！！

        a^10 = a^8*a^2

        道理很简单，对不对

if(z % 2 == 1){
    ans *= sum;
    ans %= m;
}

        OK

        二进制的单位sum自乘sum来到下一个单位

sum *= sum;
sum %= m;

         最后的最后

z /= 2;

        来到下一位

        该讲的讲完了，来到可爱的代码环节qwq

#include//头文件
using namespace std;
#define int long long
int a,b,p;
int quickpower(int d,int z,int m){//快速幂
    int ans = 1,sum = a;
    while(z){
        if(z % 2 == 1){
            ans *= sum;
            ans %= m;
        }
        sum *= sum;
        sum %= m;
        z >>= 1;
    }
    return ans;
}
signed main(){
    cin >> a >> b >> p;
    printf("%lldn",quickpower(a,b,p));
    return 0;
}

 THE END