前言
知道快速幂首先要知道（a * b）%c=（a%c）*（b%c）
还要知道 ab= a2*(b/2) = （a2）（b/2）
当换成int类型需要考虑奇偶型做不同处理
那么幂分为奇偶数考虑
- b%2=0: ab= a2*（b/2）=(a2)b/2
- b%2=1:ab=a* a2*（b/2）=a*(a2)b/2(因为b/2之后为基数数值变小了（int）类型。5/2=2，2*（5/2）=4一样)。
- 这样发现如果求余数的话就可以用递归的思想。
- 比如求2100000%7.那么就是((2%7 ) * (2%7))50000=450000=((4%7)*(4%7))25000=1625000你可以看得出这三步计算就省了近75000次计算。数值越大效果越明显。
- 下面给出java模板：
输出2n %100000007的值
非递归版
import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO 自动生成的方法存根 Scanner sc = new Scanner(System.in); int t = sc.nextInt(); for (int i = 0; i < t; i++) { long b = sc.nextLong(); long c = 1000000007; long a = 2; long res = 1; a %= c; for (; b != 0; b /= 2) { if (b % 2 == 1) res = (res * a) % c; a = (a * a) % c; } System.out.println(res); } } }
递归版（用的比较多）
import java.util.Scanner; public class Main { static long c = 1000000007; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); for (int i = 0; i < t; i++) { long a = 2; long b = sc.nextLong(); long value = divide((long) 2, b); System.out.println(value % c); } } private static long divide(long a, long b) { if (b == 0) return 1; else if (b % 2 == 0) { return divide((a % c) * (a % c), b / 2) % c; } else return a % c * divide((a % c) * (a % c), (b - 1) / 2) % c; } }
