问题描述：
求A^k mod B
输入：
包括三个正整数A，B，k ，其中1<=A<B<=10,000 ,1<=k<=2,000,000,000
输出：
一个整数表示A^k mod B的值
样例输入
2 3 1
2 3 2
样例输出
2
1
刚开始想到的一定是，用for循环来进行累乘，然后进行计算，但是k的范围过大，使得数据会溢出，所以不能用此方法来解题！
在一本书上看到的一种方法：
我们可以从k的二进制进行思考，
这是求二进制数的方法，所以A^k=(A^k/2)^2;这次应该就有思路了吧
而二进制数只能是0或1，所以如果我们用二进制数来计算表示k的话，可以发现A^k <=> A*k;
#include<stdio.h> int mod(int a,int k,int b) { int temp,ans; ans=1; temp=a; while(k!=0) { if(k%2==1) ans=ans*temp%b; //判断每一次的余数是否是1，如果是1，则把我们前面算出来的temp值乘进去 temp=temp*temp%b; //每一次更新temp的值，其实也是对每一次temp的值取余，间接的减小了temp的值 k/=2; } //计算而k的进制数 return ans; } int main() { int a,b,k; while(scanf("%d%d%d",&a,&b,&k)!=EOF) { printf("%d\n",mod(a,k,b)); } return 0; }希望对大家有帮助
