题目描述
输入b，p，k的值，求b^p mod k的值。其中b，p，k*k为长整型数。
输入输出格式
输入格式：
三个整数b,p,k.
输出格式：
输出“b^p mod k=s”
s为运算结果
输入输出样例
以b==11为例，b=>1011,二进制从右向左算，但乘出来的顺序是 a^(2^0)*a^(2^1)*a^(2^3)，是从左向右的。我们不断的让base*=base目的即是累乘，以便随时对ans做出贡献。
#include<bits/stdc++.h> using namespace std; long long b,p,k; long long mod(long long a,long long b) { long long ans=1;// 迭代记录乘积 while(b) { if(b&1) { ans*=a; ans%=k; } a*=a;//这里是关键求出了base-->base2-->base4-->base8-->base16-->base^32.......指数正是 2^i ，这岂不完美乎？ a%=k; b>>=1; } return ans; } int main() { cin>>b>>p>>k; cout<<b<<'^'<<p<<" mod "<<k<<'='<<mod(b,p)%k;//b的p次方 return 0; }
# 更新注意事项：
注意中间的取模，被坑过一次