快速幂

快速幂是很多数学题的最基本的东西，是一种可以在 $O(\log n)$ 的复杂度求解 $a^n$ 的问题的算法。

一般来说，求解 $a^n$ 的问题要循环 $n$ 次，每次乘 $a$，时间复杂度 $O(n)$。 但是快速幂用到了一个性质：任何一个正整数都可以写成几个 $2$ 的次幂的和，其实就是可以转换成二进制。 所以可以将 $a^n$ 转换成：

$$n=2^{x_1}+2^{x_2}+2^{x_3}+...+2^{x_t},t\le\log n$$

则 $a^n$ 变为：

$$a^n=a^{2^{x_1}+2^{x_2}+2^{x_3}+...+2^{x_t}}=a^{2^{x_1}}\times a^{2^{x_2}}\times a^{2^{x_3}}\times...\times a^{2^{x_t}}$$

剩下的预处理解决即可，也可以边做边出来。

因为 $t\le \log n$，所以时间复杂度是 $O(\log n)$。

注意点 1.注意取模，取模不当很容易爆。

code

P1226 【模板】快速幂

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll qpow(ll a,ll b,ll p){
	ll ans=1;
	a%=p;
	while(b){
		if(b&1){
			ans*=a%p;
			ans%=p;
		}
		a=a*a%p;
		a%=p;
		b>>=1;
	}
	return ans;
}
int main(){
	ll a,b,p;
	cin>>a>>b>>p;
	cout<<a<<'^'<<b<<" mod "<<p<<'='<<qpow(a,b,p);
	return 0;
}