查了一下書(shū),知道了這樣一個(gè)公式,這樣昨天二分法的疑問(wèn)就可以解決了,也可以用迭代法實(shí)現(xiàn)了:看來(lái)吳文虎編寫(xiě)的書(shū)還挺配套的.

也就是 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;
}
書(shū)中還說(shuō)可以提高效率,研究后再說(shuō).
(a^b)%n=(a^（b/2）%n * a^（b/2）%n)%n
根據(jù)這個(gè)公式，討論奇數(shù)和偶數(shù)處理
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;
}