整数乘方有问题?给定两个非负整数a,b和一个正整数m,求a的b次方除m的余数.要计算这个问题,可以将a连乘b次,每次都对m求余,但这种方法特别慢,当b较大时无法使用.下面给出一种较快的

Question

整数乘方有问题?
　　给定两个非负整数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
using namespace std;
int exp(int a,int b,int m)
{
@你的代码
}
我贴的代码是：
if(b==0) //0:1%m
return (1%m);
else
{
if(b%2==0) //偶数:(a^(b/2)%m)^2%m
{
int middle=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
{
int middle=1,i,q;
q=b-1;
while(q>=1)
{
middle=a*middle;
q--;
}
return middle%m*a%m;
}
}

Answer 1

我想说,其实这是一个递归问题⋯⋯
如果是我的话,会这么写程序⋯⋯还有楼主你根本没提问嘛
int exp(int a,int b,int m)
{
if(b == 0)
return 1%m;
if(b%2 == 0)
{
int t = exp(a,b/2,m);
t*=t;
return t%m;
}
else
{
int t = exp(a,b-1,m);
return (t*a)%m;
}
}