#include<bits/stdc++.h>
using namespace std;
int prime[100005],isprime[21000005],cnt=0;
bool vis[21000005];
long long getfunc(int n){
	long long tmp=n,res=1,fz=1,fm=1;
	for(register int i=0;tmp>1&&prime[i]<20000000;i++){
		if(tmp%prime[i]==0){
			fm*=prime[i];
			fz*=(prime[i]-1);
			while(tmp%prime[i]==0)tmp/=prime[i];
		}
	}
	if(tmp!=1)tmp--;
	res=n/fm*fz;
	return res;
}
int a,m,b,mod;
bool flag=0;
inline int read(){
	int ret=0,f=1;char ch;
	while((ch=getchar())<'0'||ch>'9')if(ch=='-')f=-1;
	while(ch>='0'&&ch<='9'){
		(ret=(ret<<1)+(ret<<3)+(ch^48)),ch=getchar();
		if(ret>=mod){
			flag=1;
			ret%=mod;
		}
	}
	return ret%mod*f;
}
long long pow(long long n,long long k,long long mod){
	long long p=1,q=n%mod;
	while(k){
		if(k&1)p=(p*q)%mod;
		q=(q*q)%mod;
		k>>=1;
	} 
	return p;
}
int main(){
	for(register int i=2;i<=21000000;++i){
		if(!vis[i]){
			prime[cnt++]=i;
			vis[i]=1;
			isprime[i]=1;
		}
		for(register int j=0;j<cnt;++j){
			if(i*prime[j]>21000000)break;
			vis[i*prime[j]]=1;
			if(i%prime[j]==0)break;
		}
	}
	cin>>a>>m;
	mod=getfunc(m);
	b=read();
	if(flag==1)cout<<pow(a,b+mod,m);
	else cout<<pow(a,b,m);
}

这个代码过了这道题目，但是有一个玄学问题。

可以看到，我的代码欧拉筛晒到了 $21000000$，如果我改成筛到 $20000000$（即和欧拉函数限定范围一致），会导致浮点数爆炸 RE，如果把筛的范围和欧拉函数限定范围改小，就会导致 WA。

有无大神知道是为什么（

RE,54pts

WA,76pts

RE,88pts

WA,94pts

AC