P4139

· · 个人记录

上帝与集合的正确用法

这个题还是非常巧妙的。

简单来说，我们设 s=2^{2^{2^{\cdots}}} ，则所求为： s\bmod p 。

然后我们根据某个结论可知：

s\equiv 2^{s\bmod \varphi(p)+\varphi(p)}\pmod{p}

因为这里 s>\varphi(p) 不论何时一定成立，所以上述结论一定是对的。

那这样，问题转化为了求：s\bmod \varphi(p) 。

那么同理我们可以转化为：

s \equiv 2^{s\bmod\varphi(\varphi(p))+\varphi(\varphi(p))}\pmod{\varphi(p)}

然后很显然这是个递归求解的问题。

我们知道这样子做的话 \varphi(p) 一定会越缩越小，直到 \varphi(p)=1 时，我们就可以直接求得答案了，化无限为有限了。

然后就是要注意这个 2 的次幂虽然可以用位移来写数值，，但显然当模数过大时这个位数不满足要求，，所以还是老老实实写快速幂罢。。。

关于这个时间复杂度，我们清楚这个指数在每一次递归中都会变得 <2\varphi(p)<2p ，也就是说指数的级别每次至少缩减一半。

那么我们可以得到：T(n)=T(\dfrac{n}{2})+\Theta(\log n) 。

那么时间复杂度就大概是 O(\log n) 左右。（并不会求这个，也有可能是 O(\log^2n)） 。

Update: AD20220131

应该是 O(\log^2n)。

直接求和计算：

T(n)=O(\sum_{i=1}^{\log_2n}\log _22^i)=O(\sum_{i=1}^{\log_2n}i)

就是等差数列求和，肯定就是 O(\log^2n) 的。

代码：

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

const ll N=1e7,M=7e5;

ll T,p,ans,cnt;

bool f[N+5];

ll phi[N+5],prime[M+5];

ll qpow(ll a,ll b,ll p) {
    ll res=1;
    while(b>0) {
        if(b&1) res=(res*a)%p;
        a=(a*a)%p;b>>=1;
    }
    return res%p;
}

ll solve(ll m) {
    if(m==1) return 0;
    return qpow(2,solve(phi[m])+phi[m],m);
}

void init() {
    f[1]=1;phi[1]=1;
    for(ll i=2;i<=1e7;i++) {
        if(!f[i]) {prime[++cnt]=i;phi[i]=i-1;}
        for(ll j=1;j<=cnt&&i*prime[j]<=1e7;j++) {
            f[i*prime[j]]=1;
            if(i%prime[j]) {
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
            }
            else {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
        }
    }
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    if(x<0) {x=-x;putchar('-');}
    ll y=10,len=1;
    while(y<=x) {y*=10;len++;}
    while(len--) {y/=10;putchar(x/y+48);x%=y;}
}

int main() {

    T=read();

    init();

    while(T--) {
        p=read();
        ans=solve(p);
        write(ans);putchar('\n');
    }

    return 0;
}