点击量：177

    扩展欧拉定理的应用

目录

题目描述

根据一些书上的记载，上帝的一次失败的创世经历是这样的：

 

第一天， 上帝创造了一个世界的基本元素，称做“元”。

 

第二天， 上帝创造了一个新的元素，称作“\(\alpha\)”。“\(\alpha\)”被定义为“元”构成的集合。容易发现，一共有两种不同的“\(\alpha\)”。

 

第三天， 上帝又创造了一个新的元素，称作“\(\beta\)。“\(\beta\)”被定义为“\(\alpha\)”构成的集合。容易发现，一共有四种不同的“\(\beta\)”。

 

第四天， 上帝创造了新的元素“\(\gamma\)”，“\(\gamma\)”被定义为“\(\beta\)”的集合。显然，一共会有16种不同的“\(\gamma\)”。

 

如果按照这样下去，上帝创造的第四种元素将会有\(65536\)种，第五种元素将会有\(2^{65536}\)种。这将会是一个天文数字。

 

然而，上帝并没有预料到元素种类数的增长是如此的迅速。他想要让世界的元素丰富起来，因此，日复一日，年复一年，他重复地创造着新的元素……

 

然而不久，当上帝创造出最后一种元素“\(\theta\)”时，他发现这世界的元素实在是太多了，以致于世界的容量不足，无法承受。因此在这一天，上帝毁灭了世界。

 

至今，上帝仍记得那次失败的创世经历，现在他想问问你，他最后一次创造的元素“\(\theta\)”一共有多少种？

 

上帝觉得这个数字可能过于巨大而无法表示出来，因此你只需要回答这个数对\(p\)取模后的值即可。

 

你可以认为上帝从“\(\alpha\)”到“\(\theta\)”一共创造了\(10^9\)次元素，或\(10^{18}\)次，或者干脆\(\infty\)次。

 

一句话题意：求

$$2^{2^{2^{2^{2^{2^{\dots}}}}}}\mod p$$

 

输入输出格式

输入格式：

第一行一个整数\(T\)，表示数据个数。

 

接下来\(T\)行，每行一个正整数\(p\)，代表你需要取模的值。

 

输出格式：

\(T\)行，每行一个正整数，为答案对\(p\)取模后的值

 

输入输出样例

输入样例#1：

3
2
3
6

输出样例#1：

0
1
4

说明

对于\(100\%\)的数据，\(T\le 1000,p \le 10^7\)。

题解：

    一开始，看到一句话题意，不知道这个数什么时候才会停止，不过当模数为2的幂时，答案应该都是0。不过既然取模了，就尝试用扩展欧拉定理对指数取模。

    扩展欧拉定理：

$$a^b\equiv \begin{cases}
a^{b\mod \varphi(p)}&\gcd(a,p)=1\\
a^b&\gcd(1,p)\not=1,b<\varphi(p)\\
a^{b\mod \varphi(p)+\varphi(p)}&\gcd(a,p)\not=1,b\ge \varphi(p)&
\end{cases} \mod p$$

    但是我们好像无法直接把公式套上去，因为题目给出的这个式子是无穷无尽的。但实际上这样做是行得通的，因为变到指数上去后，模数变为了\(\varphi (p)\)，一次又一次迭代使得\(p\)屡次减小，最后\(\mod 1\)或\(\mod 2\)时返回\(0\)即可。

    式子变成了

$$2^{2^{2^{2^{\cdots}\mathrm{mod} \varphi(\varphi(\varphi(p)))}\ \mathrm{mod}\ \varphi(\varphi(p))}\ \mathrm{mod}\ \varphi(p)}\ \mathrm{mod}\ p$$

    只要一直这样调用下去，每个询问只需要约\(\log p\)次就可以到达边界，总时间复杂度为\(O(T\log p)\)。线性求欧拉函数\(\varphi(x)\)方法及证明可见【学习笔记】数学小知识点。

Code：

#include<cstdio>
#include<cstring>
bool is[10100000];
int pri[3010010],cnt=0;
int phi[10100000];
int ask[1001];
long long qpow(long long x,long long y,long long p)
{
    long long ans=1,m=x;
    while(y)
    {
        if(y&1)
            ans*=m;
        ans%=p;
        m*=m;
        m%=p;
        y>>=1;
    }
    return ans;
}
long long calc(long long p)//计算2的无限次方modp
{
    if(p<=2)
        return 0;
    return qpow(2,calc(phi[p])+phi[p],p);
}
int main()
{
    memset(is,1,sizeof(is));
    int T,mx=0;
    scanf("%d",&T);
    for(int i=1;i<=T;++i)
    {
        scanf("%d",&ask[i]);//离线处理，就有了预估的上界
        mx=mx>ask[i]?mx:ask[i];
    }
    is[1]=0;
    is[0]=0;
    for(int i=2;i<=mx;++i)//线性求欧拉函数
    {
        if(is[i])
        {
            phi[i]=i-1;
            pri[++cnt]=i;
        }
        for(int j=1;j<=cnt&&i*pri[j]<=mx;++j)
        {
            is[i*pri[j]]=0;
            if(i%pri[j]==0)
            {
                phi[i*pri[j]]=pri[j]*phi[i];
                break;
            }
            else
                phi[i*pri[j]]=phi[i]*(pri[j]-1);
        }
    }
    for(int i=1;i<=T;++i)
        printf("%lld\n",qpow(2,calc(phi[ask[i]])+phi[ask[i]],ask[i]));//用快速幂协同递归
    return 0;
}