题解：UVA10692 Huge Mods

· · 题解

本题有严格弱化：苦恼的小明。

那一题数据特别水，而且没有多测。

前置知识：扩展欧拉定理。

利用该定理可以将 a^b 进行降幂。

那这题就是一个板子应用啊，我们从最内层先进行运算，然后算出来的值再作为下一层的指数，以此类推。

递归或者递推即可。

我写的递归不知名爆炸了，能过弱化过不了这题洛谷数据水的可以，于是这里给出递推的写法。

#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;
}