整数乘方有问题?

给定两个非负整数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;

}

}