快速幂取模

时间：2011-06-08 来源：胡家威

快速幂取模就是在O(logn)内求出a^n mod b的值。算法的原理是ab mod c=(a mod c)(b mod c)mod c

因此很容易设计出一个基于二分的递归算法。
以下是我的代码，以下代码必须保证输入的是合法的表达式，比如不能出现0^0 mod b：

long exp_mod(long a,long n,long b)
{
    long t;
    if(n==0) return 1%b;
    if(n==1) return a%b;
    t=exp_mod(a,n/2,b);
    t=t*t%b;
    if((n&1)==1) t=t*a%b;
    return t;
}

关于其中的一个按位与运算，来自百度知道的解释：

也就说，只有技奇数才满足这个条件 n&1==1 我的测试：

public class Test {

    public static void main(String[] args) {
        long a=3,n=100,b=2;
        long t=exp_mod(a,n,b);
        System.out.println(t);
        System.out.println((int)Math.pow(3, 100)%2);
    }
    
    public static long exp_mod(long a,long n,long b)
    {
        long t;
        if(n==0) return 1%b;
        if(n==1) return a%b;
        t=exp_mod(a,n/2,b);//注意这里n/2会带来奇偶性问题
//        System.out.println(t);
        t=t*t%b;//乘上另一半再求模
//        System.out.println(t);
        if((n&1)==1) t=t*a%b;//n是奇数，因为n/2还少乘了一次a
//        System.out.println(t);
        return t;
    }
}