算法1
(减治法)
时间复杂度 O(log2N)
递推公式 (高中数学)
a^b = (a^2)^(b/2)
-----> (a^4)^(b/4) 即 (a^2*a^2) ^ (b/2/2)
-----> (a^8)^(b/8) 即 (a^4*a^4) ^ (b/4/2)
-----> (a^16)^(b/16) 即 (a^8*a^8) ^ (b/8/2)
......
因为b是位运算操作,最终会收敛为0
翻译成代码就是
ans=1;
while b>0:
ans=ans*a;
a=a*a;
b=b/2;
Java
import java.io.BufferedInputStream;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(new BufferedInputStream(System.in));
long a = scanner.nextInt();
long b = scanner.nextInt();
long c = scanner.nextInt();
long ans = 1;
while (b>0){
if((b&1) == 1) {
ans=ans*a%c;
}
//相当于b/2
b>>=1;
a=a*a%c;
}
ans = ans%c;
System.out.println((int)ans);
}
}
C++代码
#include<iostream>
using namespace std;
using i64 = long long;
i64 b,p,k;
i64 fpow(i64 a,i64 b,i64 c){
i64 res = 1;
while(b){
if((b & 1) == 1){
res = res * a;
res %= c;
}
a = a * a;
a %= c;
b >>= 1;
}
return res % c;
}
int main(){
cin >> b >> p >> k;
auto ans = fpow(b,p,k);
printf("%lld",ans);
return 0;
}
算法2
(减治法)
时间复杂度 O(log2N)
递归的写法
分类讨论 :
1 当 b 为奇数 ,即 b%2==1 时:
a^b = a^ (c + 1) ,此时 c 必为偶数
a^b = a * ( a ^ (b - 1) )
2 当b 为偶数时,
a ^ b = (a^(b/2)) * (a^(b/2));
即
#include<iostream>
using namespace std;
using i64 = long long;
i64 b,p,k;
i64 fpow(i64 a,i64 b,i64 c){
if(b == 0){
return 1;
}
if( b % 2 == 1){
return a * fpow(a,b - 1,c) % c;
}
i64 product = fpow(a,b / 2,c);
return product * product % c;
}
int main(){
cin >> b >> p >> k;
auto ans = fpow(b,p,k);
printf("%lld",ans);
return 0;
}
兄弟有时间填个邀请码hhhhhhhhh(可以得AC币,邀请码在学生认证那填) 我的邀请码是:GUDFH