P1405 苦恼的小明

· · 题解

个人认为这题应该是绿题。

题意简述：求 a^{b^{c^{d^{...}}}} mod \ \ \ 10007 的值

看到这道题目，首先认为是快速幂，但是发现有多个乘方，而指数可能会很大，不能直接对10007取模，所以不能单纯的用快速幂水过。

所以我们就要运用欧拉定理的推论对其进行求解。

前置知识 ： 欧拉函数、欧拉定理

不会的可以自行学习

欧拉定理的推论 ：若正整数 a,n 互质，则对于任意正整数 b ,有

\ {a^{b}\equiv \ a^{b \ mod \ \varphi{(n)}} \pmod{m} }

证明如下：

设 b=q*\varphi(n)+r , 其中 0 \leqq r \leqq \varphi(n) , 即 r=b \ \ mod \ \varphi(n) 。

于是：a^{b}\equiv a^{q*\varphi(n)+r}\equiv (a^{\varphi{(n)}})^{q} * a^{r} \equiv 1^q * a^r \equiv a^r \equiv \ a^{b \ mod \ \varphi{(n)}} \pmod{m}

Q.E.D

另外，若 a,n 不互质，且b> \varphi(n)则有

\ {a^{b}\equiv \ a^{b \ mod \ \varphi{(n)}+\varphi(n)} \pmod{m} }

那么，我们对于每一个数的指数，都可以求出其对应的模数的欧拉函数,即\varphi(\text{模数}) ， 然后就可将指数的大小控制下来，再跑快速幂即可。

举个栗子： 假设 b与\varphi(n)互质

a^{b^{c^{d}}}\ mod \ 10007\equiv a^{(b^{c^{d}}\ mod \ \varphi(10007))}\ mod \ \ 10007\equiv a^{(b^{(c^{d}\ mod \ \varphi(\varphi(10007)))}\mod \varphi(10007))} \ mod \ \ 10007

所以我们可以通过递归来不断缩小每个数的指数，再返回求出每个数的值。

听不懂看代码

#include <bits/stdc++.h>
using namespace std;
long long n;
long long ask(long long m){//求m的欧拉函数 
    long long anss=m;
    for(long long i=2;i*i<=m;i++){
        if(m%i==0){
            anss=anss/i*(i-1);
            while(m%i==0) m/=i;
        }
    }
    if(m>1) anss=anss/m*(m-1);
    return anss;
}
long long a[10001000];
long long power(long long x,long long y,long long mod){//快速幂 
    long long anss=1,res=x;
    while(y){
        if(y%2) anss=anss*res%mod;
        res=res*res%mod;
        y>>=1;
    }
    return anss;
}
long long gcd(long long aa,long long bb){//求最大公约数 
    if(bb==0) return aa;
    return gcd(bb,aa%bb);
}
long long dfs(long long x,long long mod){
    if(x==n){
        return a[x]=a[x]%mod;//到了最后一个数，返回mod后的值 
    }
    long long kkk=ask(mod);//求当前模数的欧拉函数 
    long long kk=dfs(x+1,kkk);//递归下一个数 
    if(gcd(a[x],mod)==1) return a[x]=power(a[x],kk,mod);//两数互质 
    else {
        if(a[x+1]>kkk) return a[x]=power(a[x],kk+kkk,mod);//指数大于phi[mod]，用欧拉定理 
        return a[x]=power(a[x],a[x+1],mod);//指数小于phi[mod]直接快速幂，不能用欧拉定理 
    }
}
int main(){
//  freopen("data.in","r",stdin);
//  freopen("my.out","w",stdout);
    scanf("%lld",&n);
    for(long long i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    printf("%lld\n",dfs(1,10007));
    return 0;
}