洛谷 P4139 上帝与集合的正确用法 题解

洛谷 P4139 上帝与集合的正确用法 题解

2020-2-26 xiaoh

题意

有$t$个询问($1\leq t\leq 1000$),每个询问给定一个正整数$p$($1\leq p\leq 10^7$),求

$2^{2^{2^{...}}}\,mod\;p$

的值.

题解

看到好多好多的指数幂,下意识的想到欧拉定理.那么接下来考虑一下复杂度的问题.我们先证明一下命题:
假设$f(a,b)=\varphi(\varphi(...\varphi(b)))(a个\varphi函数)$ 的值一定在 $\log b$级别的时间内变为1.
证明很简单:
对于所有的奇数,取一次 $\varphi$后至少减$1$,且一定会变为偶数;
对于所有偶数,取一次 $\varphi$后至少减半(即所有偶数全部去掉).
所以在$2\log b$的时间内,函数值一定会变为$1$,那么我们直接暴力的一层一层往上推,当推到该层的模数为$1$时,答案就会变为$0$,套个快速幂的模板即可.注意到暴力求欧拉函数值是$O(\sqrt n)$ 的,所以复杂度就变成了$O(t\log^2 n+t\log n\sqrt p)$,然后复杂度就上天了……连氧气都拉不回来那种QAQ
所以我们考虑采用埃氏筛法预处理出 $[1,10^7]$ 之间的欧拉函数值,然后直接调用,时间复杂度$O(n\log\log n+t\log^2 n)$.

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
    x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    return;
}
template<typename T>
inline void write(T x)
{
    if(x>=10) write(x/10);
    putchar(x%10+'0');
}
const int MAXN=10000010;
int n;
int tot=0;
int f[MAXN];
inline int pow_mod(int a,int b,int k)//快速幂
{
    if(b==0) return 1;
    if(b==1) return a%k;
    int tmp=pow_mod(a,b>>1,k);
    tmp=(int)((long long)tmp*(long long)tmp%(long long)k);
    if(b&1) tmp*=a,tmp%=k;
    return tmp;
}
inline int cal(int mod)//递归计算答案
{
    if(mod==1) return 0;
    int x=f[mod];
    return pow_mod(2,x+cal(x),mod);
}
int main()
{
    for(int i=1;i<=10000000;i++) f[i]=i;//预处理出欧拉函数值
    for(int i=2;i<=10000000;i++)
    if(f[i]==i)
    for(int j=1;i*j<=10000000;j++) f[i*j]=f[i*j]/i*(i-1);
    int t;
    read(t);
    while(t--)
    {
        read(n);
        write(cal(n)),putchar('\n');
    }
}