Pilot's Blog
0%

Acwing875快速幂

发表于 更新于 分类于 ， ， Valine：
本文字数： 1k 阅读时长 ≈ 1 分钟
快速幂，但还是得防止超时

题目

分析

快速幂，虽然java开BigInteger可以防止爆栈，但是会超时

引理

因为有上面的引理，所以在每次求快速幂的过程中都可以取余

代码

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
26
import java.util.Scanner;
import java.math.BigInteger;
public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int a = scan.nextInt();
		int b = scan.nextInt();
		int p = scan.nextInt();
		System.out.println(quickPower(a, b, p));
		scan.close();
	}
	static BigInteger quickPower(int base, int power, int p) {
		BigInteger baseBigInteger = new BigInteger(String.valueOf(base));
		BigInteger powerInteger = new BigInteger(String.valueOf(power));
		BigInteger pBigInteger = new BigInteger(String.valueOf(p));
		BigInteger ansBigInteger = BigInteger.ONE;
		while(powerInteger.compareTo(BigInteger.ZERO) > 0) {
			if(powerInteger.and(BigInteger.ONE).compareTo(BigInteger.ZERO) > 0) {
				ansBigInteger = ansBigInteger.multiply(baseBigInteger).mod(pBigInteger);	//取余1
			} 
			baseBigInteger = baseBigInteger.multiply(baseBigInteger).mod(pBigInteger);	//取余2
			powerInteger = powerInteger.shiftRight(1);
		}
		return ansBigInteger.mod(pBigInteger);
	}
}