快速幂

题目：求 a^n % p。

分析：a^n = a^(2^0 * n[0] + 2^1 * n[1] + 2^2 * n[2] + ... + 2^(t-1) * n[t-1])

                 = (a^(2^0))^n[0] * (a^(2^1))^n[1] * (a^(2^2))^n[2] * ... * (a^(2^(t-1)))^n[t-1]

           其中，t = log(n)，n[i] = 0或1

代码：

public class OJ {
    public static void main(String[] args) {
        OJ oj = new OJ();
        System.out.println(oj.power(2147483647, 2147483647, 17));
    }
    
    private long power(long a, long n, long p) {
        long ans = 1;
        long tmp = a % p;
        while (0 != n) {
            if (0 != (1 & n)) {
                ans = ans * tmp % p;
            }
            
            n >>= 1;
            tmp = tmp * tmp % p;
        }
        
        return ans;
    }
}