洛谷 P4139 上帝与集合的正确用法 题解【欧拉函数】【数学】

作者: wjyyy 分类: 数学,欧拉函数,解题报告 发布时间: 2018-09-07 14:51

点击量:24

 

    扩展欧拉定理的应用

 

题目描述

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

 

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

 

第二天, 上帝创造了一个新的元素,称作“\(\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;
}

说点什么

avatar
  Subscribe  
提醒
/* */