乘方
问题描述：
求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;
}
希望对大家有帮助
相关阅读
一个网站的关键词排名最快的应该是做竞争推广，但是这种方式需要的成本会比较高。而自然排名的关键词优化则是相对成本比较少的。不
simple-quartz-tasks基于quartz的任务调度插件，引入到spring项目中实现任务信息装载接口即可使用，依赖于redis的订阅完成对任务的立
本文来自作者 木木小迷哥 在 GitChat 上分享「Matlab GUI 零基础学员快速入门」，「阅读原文」查看交流实录「文末高能」编辑
大白NB-IOT 移远BC28模块模组快速入门 （教您10分钟打通
今天大白来为大家详细介绍我们的大白BC28评估板的快速入门指南。 文末有彩蛋！！！
Spring Cloud Ribbon 是一个基于ＨTTP和TCP的客户端负载均衡工具，它基于Netflix Ribbon实现。通过 Spring Cloud 的封装， 可以让我们