费马小定理：
当 $a,p \in \mathbb{Z} $ 且 \(p\) 为质数，$a \not\equiv 0 \pmod{p} $ 时，有：
\[a^{p-1} \equiv 1 \pmod{p} \]故 \(a^b \equiv a^{b \mod (p-1)} \pmod{p}\)
欧拉定理：
当 $a,p \in \mathbb{Z} $ 且 \(\gcd(a,m)=1\) 时，有：
\[a^{\varphi(m)} \equiv 1 \pmod m \]其中 \(\varphi(m)\) 为数论中的欧拉函数，即 \(1 \sim n\) 中与 \(n\) 互质的数的个数。
所以 \(a^{b} \equiv a^{b \mod \varphi(m)} \pmod m\).
扩展欧拉定理：
当 \(a,p \in \mathbb{Z}\) 时，有：
\[a^b\equiv \left\{\begin{matrix} a^b,b < \varphi(m)\\ a^{b \mod \varphi(m)+\varphi(m)}.b \geq \varphi(m) \end{matrix}\right. \pmod{m} \]模板题code：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a,m,phi=1;
int bm,flag;
int mul(int a,int b){int res=1;while(b) ((b&1)&&(res=1ll*res*a%m,0)),a=1ll*a*a%m,b>>=1;return res;}
int main()
{
scanf("%d%d",&a,&m);a%=m;int tmp=m;
for(int i=2;i*i<=tmp;i++)
{
if(tmp%i) continue;
phi*=i-1;tmp/=i;
while(tmp%i==0) phi*=i,tmp/=i;
}
if(tmp>1) phi*=tmp-1;char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(bm=bm*10ll+(ch^'0'),(ch=getchar())>='0'&&ch<='9')
if (bm>=phi) flag=1,bm%=phi;
if(bm>=phi) flag=1,bm%=phi;
if(flag) bm+=phi;
printf("%d",mul(a,bm));
return 0;
}