快速幂算法

问题说明:

/*
* 求 a 的 b 次方对 p 取模的值。

输入格式
三个整数 a,b,p ,在同一行用空格隔开。

输出格式
输出一个整数，表示a^b mod p的值。

数据范围
1≤a,b,p≤109
输入样例：
3 2 7
输出样例：
2

输入样例2:

126348976 982638476 938420413

输出样例:

701649771

* */
//题目来源： https://www.acwing.com/problem/content/91/

参考文章

说明:

1. 我们在计算3¹⁵时，如果循环乘15次，则时间复杂度时n。 另一种方法是，先把15化成二进制，为1111, 我们分别计算3¹，3²，3⁴（用前一步3²的值平方一下来计算，而不是从头计算），3⁸（用前一步3⁴值平方一下来计算，而不是从头计算), 再把这四个值乘起来，我们就得到3^15，这样我们实际只做了4次乘法，最后再将这些数乘起来，时间复杂度为LogN级别。快速幂算法就是基于这样的思想，复用前面的计算结果，快速计算一个数的大次幂。

2. 注意以下求模公式:

a^b mod c = (a mod c)^c mod c

代码:

import java.io.*;


//题目来源： https://www.acwing.com/problem/content/91/
public class 快速幂算法求m的k次方对p取模 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
        while(true) {
            String[] parts = bf.readLine().split(" ");
            //用long型接收，防止大数据溢出: 126348976 982638476 938420413
            long m = Integer.valueOf(parts[0]);
            long k = Integer.valueOf(parts[1]);
            long p = Integer.valueOf(parts[2]);

            long res = 1 % p; //防止k == 0, 不走底下的循环
            m %= p;
            while (k != 0) {
                if ((k & 1) == 1)
                    res = res * m % p;
                k >>= 1;
                m = m * m % p;
            }
            log.write(String.valueOf(res)+ '
');
            log.flush();
        }
    }
}