快速幂算法

问题说明:

/*
* 求 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

代码:

 1 import java.io.*;
 2 
 3 
 4 //题目来源： https://www.acwing.com/problem/content/91/
 5 public class 快速幂算法求m的k次方对p取模 {
 6     public static void mainString[] args) throws IOException {
 7         BufferedReader bf = new BufferedReadernew InputStreamReaderSystem.in));
 8         BufferedWriter log = new BufferedWriternew OutputStreamWriterSystem.out));
 9         whiletrue) {
10             String[] parts = bf.readLine).split" ");
11             //用long型接收，防止大数据溢出: 126348976 982638476 938420413
12             long m = Integer.valueOfparts[0]);
13             long k = Integer.valueOfparts[1]);
14             long p = Integer.valueOfparts[2]);
15 
16             long res = 1 % p; //防止k == 0, 不走底下的循环
17             m %= p;
18             while k != 0) {
19                 if k & 1) == 1)
20                     res = res * m % p;
21                 k >>= 1;
22                 m = m * m % p;
23             }
24             log.writeString.valueOfres)+ '
');
25             log.flush);
26         }
27     }
28 }

TALK IS CHEAP, SHOW ME THE CODE