题面

题意

输入正整数a1,a2,a3..an和模m，求a1^a2^...^an mod m

Sol

首先有\[ a^b\equiv \begin{cases} a^{b\%\phi(p)}~~~~~~~~~~~gcd(a,p)=1\\ a^b~~~~~~~~~~~~~~~~~~gcd(a,p)\neq1,b<\phi(p)\\ a^{b\%\phi(p)+\phi(p)}~~~~gcd(a,p)\neq1,b\geq\phi(p) \end{cases}~~~~~~~(mod~p) \]

递归处理，每次取\(\varphi\)，可以试乘来判断是否会大于\(\varphi\)大于时加上就好了

# include 
    
     # define RG register# define IL inline# define Fill(a, b) memset(a, b, sizeof(a))using namespace std;typedef long long ll;IL ll Read(){    RG ll x = 0, z = 1; RG char c = getchar();    for(; c < '0' || c > '9'; c = getchar()){        if(c == '#') exit(0);        z = c == '-' ? -1 : 1;    }    for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);    return x * z;}int n, m, a[20];IL int Phi(RG int x){    RG int cnt = x;    for(RG int i = 2; i * i <= x; ++i){        if(x % i) continue;        while(!(x % i)) x /= i;        cnt -= cnt / i;    }    if(x > 1) cnt -= cnt / x;    return cnt;}IL int Pow(RG ll x, RG ll y, RG ll p){    RG int flg2 = 0, flg1 = 0; RG ll cnt = 1;    for(; y; y >>= 1){        if(y & 1) flg1 |= (cnt * x >= p || flg2), cnt = cnt * x % p;        flg2 |= (x * x >= p); x = x * x % p;    }    return cnt + flg1 * p;}IL int Calc(RG int x, RG int p){    if(x == n) return Pow(a[x], 1, p);    return Pow(a[x], Calc(x + 1, Phi(p)), p);}int main(RG int argc, RG char* argv[]){    for(RG int Case = 1; ; ++Case){        m = Read(); n = Read();        printf("Case #%d: ", Case);        for(RG int i = 1; i <= n; ++i) a[i] = Read();        printf("%d\n", Calc(1, m) % m);    }    return 0;}