【整数乘方有问题?给定两个非负整数a,b和一个正整数m,求a的b次方除m的余数.要计算这个问题,可以将a连乘b次,每次都对m求余,但这种方法特别慢,当b较大时无法使用.下面给出一种较快的】
3人问答
问题描述：
整数乘方有问题?
给定两个非负整数a,b和一个正整数m,求a的b次方除m的余数.
要计算这个问题,可以将a连乘b次,每次都对m求余,但这种方法特别慢,当b较大时无法使用.下面给出一种较快的算法(用a^b表示a的b次方)：
若b=0,则a^b%m=1%m.
若b为偶数,则a^b%m=(a^(b/2)%m)^2%m,即先把a乘b/2次方对m求余,然后再平方后对m求余.
若b为奇数,则a^b%m=(a^(b-1)%m)*a%m,即先求a乘b-1次方对m求余,然后再乘a后对m求余.
这种方法速度较快,请使用这种方法计算a^b%m,其中m不大于10000.
这是一道完善程序的试题,你只需要在下面程序标注的“@你的代码”的位置补充适当的语句或语句段使程序能正确运行即可,在提交的时候,你要提交的内容只包括补充的内容,不包括其他的代码.
#include
#include
#include
usingnamespacestd;
intexp(inta,intb,intm)
{
@你的代码
}
我贴的代码是：
if(b==0)//0:1%m
return(1%m);
else
{
if(b%2==0)//偶数:(a^(b/2)%m)^2%m
{
intmiddle=1,i,q;//在复合语句中定义的变量作用域为复合语句
q=b/2;
while(q>=1)
{
middle=a*middle;
q--;
}
return(middle%m)*(middle%m)%m;
}
else//奇数:a^(b-1)%m*a%m
{
intmiddle=1,i,q;
q=b-1;
while(q>=1)
{
middle=a*middle;
q--;
}
returnmiddle%m*a%m;
}
}
陈会勇回答：
我想说,其实这是一个递归问题⋯⋯如果是我的话,会这么写程序⋯⋯还有楼主你根本没提问嘛intexp(inta,intb,intm){if(b==0)return1%m;if(b%2==0){intt=exp(a,b/2,m);t*=t;returnt%m...
陈会勇回答：
因为你的问题实在很简单……你的方法不是递归，是在计算a的b次幂，那你想想，如果a的b次幂非常大，大到int类型无法容纳，那你的程序还能正确吗？用递归算法虽然可能消耗内存多些，但是至少不会出现这int无法容纳的问题所以我怀疑你没通过可能是因为你的测试用例不够而已，比如你试试a=999,b=888能通过嘛，但是递归可以……我不牛啦……只是你的问题比较简单，我经验比你丰富那么一点点而已
其它推荐
其它推荐
最新更新
精品分类
优秀其它推荐
热门其它
邮箱： 