快速幂
由于数的结合律，$a^{2x}=(a^x)^2$，$a^{2x+1}=(a^x)^2 \times a$，可以使用倍增法快速求解。
ll qpow(ll a,int x,ll P){
if(x==0)return 1%P;
ll ans=1;
while(x){
if(x&1)ans=ans*a%P;
a=a*a%P;
x>>=1;
}
return ans;
}例题
| 名称 | 编号 | 备注 | 题解 |
|---|---|---|---|
由于数的结合律，$a^{2x}=(a^x)^2$，$a^{2x+1}=(a^x)^2 \times a$，可以使用倍增法快速求解。
ll qpow(ll a,int x,ll P){
if(x==0)return 1%P;
ll ans=1;
while(x){
if(x&1)ans=ans*a%P;
a=a*a%P;
x>>=1;
}
return ans;
}| 名称 | 编号 | 备注 | 题解 |
|---|---|---|---|