写成一般用 ```while``` 的形式,递归计算会重复计算,也可用记忆化加快速度。
```cpp
#include<iostream>
using namespace std;
#define int long long
int a,b,p;
int quick_pow(int a,int b,int p){
int res=1,base=a;
while(b>0){
if(b&1) res=res*base%p;
base=base*base%p;
b/=2;
}
return res;
}
signed main(){
cin>>a>>b>>p;
printf("%lld^%lld mod %lld=%lld",a,b,p,quick_pow(a,b,p));
return 0;
}
```
by Super_excavator @ 2024-01-28 21:00:20
@[KomorKomor](/user/1106289)
```ll ans=((fpow(a,b>>1,p)%p)%p*(fpow(a,b>>1,p)%p)%p)%p;```
这里 `fpow` 被调用了两次,可以使用一个变量赋值为 ```fpow(a,b>>1,p)%p```,然后平方,应该就不会 TLE 了。
~~其实不用写这么多 `%p` 啊。~~
by zhouzihang1 @ 2024-01-28 21:01:27
@[zhouzihang1](/user/827018) 是这样的,谢谢大佬
by KomorKomor @ 2024-01-28 21:02:49