题解：UVA10692 Huge Mods

#include<bits/stdc++.h>
#define int long long
int mod;
using namespace std;
int phi[10000005];
int sump[10000005];
bool is_p[10000005];
vector<int>v; //第i个质数 
void Phi(int n){
	int p=0;
	is_p[0]=1;
	is_p[1]=1;
    phi[1]=1;
    sump[1]=1;
	for(int i=2;i<=n;i++){
	    if(!is_p[i]){
            v.push_back(i);
	        for(int j=i;j*i<=n;j++)
                is_p[j*i]=1;
            phi[i]=i-1;
	    }
        for(int j=0;j<v.size()&&v[j]*i<=n;j++)
            phi[v[j]*i]=phi[i]*(v[j]-(i%v[j]!=0));
        sump[i]=sump[i-1]+phi[i];
    }
}
#define flc_INF LLONG_MAX
int qpow(int a,int b,int p=flc_INF){
	int ans=1;
    bool flag=0;
	if(b==0)return 1;
	while(b){
		if(b&1)ans*=a,flag|=(ans>=p),ans%=p;
		a*=a,b>>=1,flag|=(a>=p),a%=p;
	}
	return ans+flag*p;
}
int a[1234600];
int pp[1234600];
int n;
signed main(){
    Phi(1000000);
    int T=0;
    while(cin>>mod>>n){
        pp[1]=mod;
        for(int i=2;i<=n;i++)
            pp[i]=phi[pp[i-1]];
        for(int i=1;i<=n;i++)
            cin>>a[i];
        for(int i=n-1;i;i--)
            a[i]=qpow(a[i],a[i+1],pp[i]);
        printf("Case #%d: %d\n",++T,a[1]%mod);
    }
    return 0;
}