查了一下书,知道了这样一个公式,这样昨天二分法的疑问就可以解决了,也可以用迭代法实现了:看来吴文虎编写的书还挺配套的.

也就是 a^b%n=((a^b-1)*a)%n====>(a*b)%n=((a%n)*b)%n===>a^b%n=(((a^(b/2))%n)*a^(b/2))%n
//迭代法
int modexp2(int a,int b,int n)
{
    int r;
    r=a%n;
    for(int i=0;i<b-1;i++)
        r=(r*a)%n;
    return r;
}
书中还说可以提高效率,研究后再说.
(a^b)%n=(a^（b/2）%n * a^（b/2）%n)%n
根据这个公式，讨论奇数和偶数处理
int modExp(int a, int b, int n)
{
    int d=1,r=a;
    while(b){
        if(b%2==1){d=d*r%n;}
        r=r*r%n;
        b=b/2;
    }
    return d;
}