快速幂模板（java）

前言

知道快速幂首先要知道（a * b）%c=（a%c）*（b%c）
还要知道 a^b= a^2*(b/2) = （a²）^（b/2）
当换成int类型需要考虑奇偶型做不同处理
那么幂分为奇偶数考虑

1. b%2=0: a^b= a^2*（b/2）=(a²)^b/2
2. b%2=1:a^b=a* a^2*（b/2）=a*(a²)^b/2(因为b/2之后为基数数值变小了（int）类型。5/2=2，2*（5/2）=4一样)。

• 这样发现如果求余数的话就可以用递归的思想。
• 比如求2¹⁰⁰⁰⁰⁰%7.那么就是((2%7 ) * (2%7))⁵⁰⁰⁰⁰=4⁵⁰⁰⁰⁰=((4%7)*(4%7))²⁵⁰⁰⁰=16²⁵⁰⁰⁰你可以看得出这三步计算就省了近75000次计算。数值越大效果越明显。
  下面给出java模板：
  输出2ⁿ %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);
		}
	}
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
 

递归版（用的比较多）

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;
	}
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
 

如果对后端、爬虫、数据结构算法等感性趣欢迎关注我的个人公众号交流：bigsai

文章来源: bigsai.blog.csdn.net，作者：Big sai，版权归原作者所有，如需转载，请联系作者。

原文链接：bigsai.blog.csdn.net/article/details/84196079