快速幂核心
a^b mod c=(a^2)^(b/2) mod c (b为偶数)；
a^b mod c=((a^2)^(b div 2)*a) mod c (b为奇数)
以一道题为例，讲解快速幂算法。
题目：计算a^b mod c
朴素算法：直接计算求值。
var a,b,c,i,ans:longint;
begin
readln(a,b,c);
ans:=1;
fori:=1 to b do
ans:=ans*a;
ans:=ans mod c;
writeln(ans);
end.
以上算法有一个缺点：当a，b很大时，容易超出longint范围。
因为a^b mod c=(a mod c)^b mod c
得出改进型算法：在计算过程中不断进行mod运算
var a,b,c,i,ans:longint;
begin
readln(a,b,c);
a:=a mod c;
ans:=1;
fori:=1 to b do
ans:=(ans*a) mod c;
ans:=ans mod c;
writeln(ans);
end.
时间复杂度：O(n)
这种算法也有一定缺陷：当c很大时，容易超时。
因为a^b mod c=(a^2)^(b/2) mod c (b为偶数)；
a^b mod c=((a^2)^(b div 2)*a) mod c (b为奇数)
所以可以在计算过程中不断地将底数平方、指数除以2，用另一个变量记录最终答案。
得到快速幂算法：
var a,b,c,ans:int64;
begin
readln(a,b,c);
write(a,'^',b,' mod ',c,'=');
a:=a mod c;
ans:=1;
while b>0 do
begin
if bmod 2=1 then ans:=ans*a mod c;
b:=bdiv 2;
a:=(a*a)mod c;
end;
writeln(ans);
end.
时间复杂度：O(log2n),能在竞赛通过几乎全部的数据，是目前最常用的算法之一。
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static BigInteger result(BigInteger x,BigInteger y,BigInteger z)//快速幂
{
BigInteger sum=BigInteger.ONE;
while(y.compareTo(BigInteger.ZERO)==1)
{
if(y.mod(BigInteger.valueOf(2)).compareTo(BigInteger.ONE)==0)
{
sum=sum.multiply(x);
sum=sum.mod(z);
}
y=y.divide(BigInteger.valueOf(2));
x=x.multiply(x);
x=x.mod(z);
}
return sum;
}
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int cases=scanner.nextInt();
while(cases--!=0)
{
BigInteger a,b,c;
a=scanner.nextBigInteger();
b=scanner.nextBigInteger();
c=scanner.nextBigInteger();
System.out.println(result(a,b,c));
}
}
}