可以分治，将 $a^n$ 变成 $a^{frac{n}{2}}\times a^{frac{n}{2}}$，但如果此时 $n$ 是奇数，则多乘一个 $a$。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b,p=1e9+7;
ll qpow(ll a,ll b,ll p){
	ll res=1,tmp=a;
	while(b){
		if(b&1)res=(res%p*tmp%p)%p;
		tmp=(tmp*tmp)%p;
		b>>=1;
	}
	return res;
}
int main(){
	cin>>a>>b>>p;
	cout<<qpow(a,b,p)<<endl;
	return 0;
}

知识点：快速幂

递归公式（分治思想）：

$x^y=(x^{\lfloor\frac{y}{2}\rfloor})^2\cdot x^{y-2\cdot{\lfloor\frac{y}{2}\rfloor}}$，而终止条件为 $y=0$，此时 $x^y=1$。

即：

$x^y=\begin{cases} (x^{\frac{y}{2}})^2\qquad(2\mid y)\\ (x^{\frac{y-1}{2}})^2\cdot x(2\nmid y)\\ 1\qquad\qquad(y=0) \end{cases}$

代码如下：

int qpow(int a,int b){//即a^b
    if(b==0) return 1;//终止条件
    else if(b%2==0){
        int k=qpow(a,b/2);
        return k*k%MOD;
    }
    else{
        int k=qpow(a,b/2);
        return k*k%MOD*a%MOD;
    }
    //分治思想
}

我曾经写过一个及其精彩的错误代码：

int qpow(int a,int b){//即a^b
    if(b==0) return 1;//终止条件
    else if(b%2==0){
        return qpow(a,b/2)*qpow(a,b/2)%MOD;
    }
    else{
        return qpow(a,b/2)*qpow(a,b/2)%MOD*a%MOD;
    }
    //分治思想
}

本代码有什么问题？（设问的修辞手法）

答：这里。

return qpow(a,b/2)*qpow(a,b/2)%MOD;

以及：

return qpow(a,b/2)*qpow(a,b/2)%MOD*a%MOD;

这里相当于计算了两次qpow(a,b/2)。

所以需要乘 $b$ 次 $a$。

那么此“快速”幂的复杂度为 $O(b)$。

真正的快速幂的复杂度约为 $O(\log{b})$

用上面的那个即可通关。

#include<iostream>
using namespace std;
int main (){
    int a, b, p;
    int ans = 1;
    scanf("%d%d%d", &a, &b, &p);
    while(b){
        if(b & 1)
            ans = (long long) ans * a % p;
        a = (long long) a * a % p;
        b >>= 1;
    }
    printf("%d", ans % p);
    return 0;
}

代码自认为十分好懂

#include<cstdio>
using namespace std;
#define ll long long
ll cal(ll a, ll b, ll p)
{
    ll ans = 1 % p;
    for (; b; b >>= 1)//个人码风原因，也可使用while循环额外加b >>= 1
    {
        if (b & 1)
            ans = ans * a % p;//及时取模防止爆掉
        a = a * a % p;//及时取模防止爆掉
    }
    return ans;
}
int main()
{
	ll a, b, p;
	scanf("%lld %lld %lld", &a, &b, &p);
	printf("%lld", cal(a, b, p));
    return 0;
}

快速幂 - OI Wiki (oi-wiki.org)

#include<bits/stdc++.h>
using namespace std;
  
int main()
{
    unsigned long long a,b,mode ;
    cin>>a>>b>>mode;
    int sum=1;
    a =a%mode;
    while(b>0)
	{
        if (b%2==1)
		{
			sum =(sum*a)%mode;
		}
        b /= 2;
        a = (a * a) % mode;

   }
cout<<sum;
}

快速幂的基本原理是简单的：欲计算 $a^b$ 的值，只需计算 $a^{b/2}$ 的值即可。

在数论题当中，时常涉及到乘法的取模运算。这里用到一个原理：

$$(a\times b)\,\bmod p= [(a\,\bmod p)\times(b\,\bmod p)]\,\bmod p $$

int solve(int a,int b){
	if(b==0) return 1;
	if(b==1) return a%p;
	if(b%2==0){
		int tmp = solve(a,b>>1); //必须预存tmp的值，否则程序的效率与普通乘幂无异
		return (tmp*tmp)%p;
	}else{
		int tmp = solve(a,b>>1);
		return (tmp*tmp*(solve(a,1))%p)%p;
	}
}

板子题，直接放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a,b,m;
int power(int a,int b,int m){
    long long ans=1;
    while(b){
        if(b&1){
            ans=ans*a%m;
        }
        a=a*a%m;
        b>>=1;
    }
    return ans;
}
signed main(){
   cin>>a>>b>>m;
   cout<<power(a,b,m);
}

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b,p=1e9+7;
ll qpow(ll a,ll b,ll p){
	ll res=1,tmp=a;
	while(b){
		if(b&1)res=(res%p*tmp%p)%p;
		tmp=(tmp*tmp)%p;
		b>>=1;
	}
	return res;
}
int main(){
	cin>>a>>b>>p;
	cout<<qpow(a,b,p)<<endl;
	return 0;
}

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b,p=1e9+7;
ll qpow(ll a,ll b,ll p){
	ll res=1,tmp=a;
	while(b){
		if(b&1)res=(res%p*tmp%p)%p;
		tmp=(tmp*tmp)%p;
		b>>=1;
	}
	return res;
}
int main(){
	cin>>a>>b>>p;
	cout<<qpow(a,b,p)<<endl;
	return 0;
}

题目大意

给出 $a$, $b$, $p$。求 $a^b\bmod p$。

做法

注意到 $b\leq 2^{31}$ ,所以我们最好可以有一个$\mathit{O(logn)}$的算法来求快速幂。那么，分治，它来了。

详细介绍

接下来，就是思考如何用分治解决这个题目。当我们求 $a^b\bmod p$ 时，我们可以把原式子分为两个 $a^{b/2}\bmod p$ 的积, 如果 $b\equiv1\pmod{2}$ ,还得乘上一个 $a$ 才能等于 $a^b\bmod p$ 。这样递归下去，我们就能实现分而治之了。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int x,y,p;
int pw(int x,int y,int p){
	int re=1;
	while(y){
		if(y&1) re=re*x%p;//y&1是判y的奇偶性
		x=x*x%p;
		y>>=1;//等同于y/=2
	}
	return re;
} 
signed main(){
	cin>>x>>y>>p;
	cout<<pw(x,y,p)<<endl;
	return 0;
}

完结，撒花！！！

此题解是 JuliaRoadmap 项目的一部分

题解里很多人用递归的方法，这里不再阐述。注意到可以对$b$ 进行二进制拆分，例如对于$12=(1100)_2$，只需从左到右循环即可

题目中限定 $b<2^{31}$，使用以下代码

function main()
    a=parse(Int, readuntil(stdin,' '))
    b=parse(Int, readuntil(stdin,' '))
    p=parse(Int, readline())
    a%=p
    ans=1
    for i in 31:-1:0
        sign=(b>>i)&1 # 位运算技巧
        if sign==0
            ans=ans*ans%p
        else
            ans=(ans*ans%p)*a%p
        end
    end
    print(ans)
end
main()

评测结果492~614ms

自认为代码很通俗

首先，直接算是肯定不行的，我们要一步一步来

相关知识请看 OI Wiki

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long b,p,k;
    cin >> b >> p >> k;
    long long ans = 1;
    while (p != 0){
        if(p % 2 !=0)ans = ans * b % k;
        p /= 2;
        b = b * b % k;
    }
    cout << ans;
}

核心代码一行的快速幂：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a, b, p;
ll power (ll a, ll b, ll p) {
	return b == 0? 1: (b & 1? a: 1) * power (a * a % p, b >> 1, p) % p;
}
int main () {
    scanf ("%lld%lld%lld", &a, &b, &p);
    printf ("%lld", power (a, b, p));
    return 0;
}

压行（164B）！

#import<iostream>
typedef long long L;L a,b,p;L P(L a,L b,L p){return b?(b&1?a:1)*P(a*a%p,b/2,p)%p:1;}int main(){std::cin>>a>>b>>p;std::cout<<P(a,b,p);return 0;}

顺便找了一个不递归的压了压（182B）：

#import<iostream>
typedef long long L;L a,b,p;L P(L a,L b,L p){L S=1;while(b){if(b&1)S=S*a%p;a=a*a%p;b/=2;}return ans;}int main(){std::cin>>a>>b>>p;std::cout<<P(a,b,p);return 0;}

可以发现，前者代码短一点。

（喂喂我这个大码量人为什么要玩 Code Golf 啊

Hydro H1032【模板】快速幂 & 洛谷 P1226 题解

#include<iostream>
using namespace std;
long long a,b,p,q,w;
int loop(long long x,long long y)
{
    if(y==0)
    {
        return 1;
    }
    long long res=1;
    while(y)
    {
        if(y&1)
        {
            res=res*x%p;  /*需要%*/
        } 
        x=x*x%p;  /*需要%*/
//      cout<<x<<endl;
        y>>=1;
    } 
    return res;
}

int main()
{
    cin>>a>>b>>p;
    q=loop(a,b);
    w=q % p;
    cout<<w<<endl;
}

整点最短解。以下是利用 python3 完成的一个很短的写法（37 B）：

print(pow(*map(int,input().split())))

其实很简单。。。

#include<iostream>
using namespace std;
#define int long long
int a,b,p;
int power(int a,int b,int p){
	int ans=1;
	while(b){
		if(b&1==1)ans=ans*a%p;
		a=a*a%p;
		b>>=1;
	}return ans;
}
signed main(){
	cin>>a>>b>>p;
	cout<<power(a,b,p);return 0;
}

使用分治思想，每次将指数 $n$ 减半，再平方。但如果 $n$ 是技术，则要再乘 $a$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
inline ll read()
{
	ll x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
ll quickpow(ll a,ll b,ll m){
	if(b==0)  return 1;
	ll tmp=quickpow(a,b/2,m)%m;
	ll ans=tmp*tmp%m;
	if(b&1)  ans=ans*a%m;
	return ans; 
}
int main(){
	ll a,b,p;
	a=read(),b=read(),p=read();
	cout<<quickpow(a,b,p);
	return 0;
}

注释了啊

我第一次在这里做的

#include <bits/stdc++.h>
using namespace std;
/*
(a+b)%k = (a%k+b%k)%k
(a*b)%k = ((a%k)*(b%k))%k 
*/

//快速幂  (a^x)%p
// a=1231321313
// x=5464646546
// p=12313 

long long a,x,p;

long long f(int k){//a的k次方 %p的结果 
	if(k==0) return 1;
	if(k==1) return a%p;
	long long tmp=f(k/2);
	if(k%2==0){
		return tmp*tmp%p;
	}else{
		return (tmp*tmp%p)*a%p;
	}
}

int main(){
	cin>>a>>x>>p;
    cout<<f(x);
    return 0;
}

位运算 code

#include<stdio.h>
using namespace std;
unsigned long long a,b,mod;
unsigned long long pow(unsigned long long a,unsigned long long b){
    unsigned long long ret = 1;
    while(b){
        if(b&1)
            ret=(ret*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return ret;
}
int main(){
    scanf("%lld%lld%lld",&a,&b,&mod);
    printf("%lld",pow(a,b)%mod);
return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a,b,p;
int qp(int a,int b,int p)
{
	int res=1;
	while(b)
	{
		if(b&1)
		{
			res*=a;
			res%=p;
		}
		a*=a;
		a%=p;
		b>>=1;
	}
	return res;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>a>>b>>p;
	cout<<qp(a,b,p);
	cout.flush();
	return 0;
}

板子，就不说了，直接背