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

题目链接：P4139 上帝与集合的正确用法

题意：

有无穷数列 \[ a_0=1,a_n=2^{a_{n-1}} \] 当 \(n \to +\infty\) 时，计算 \[ a_n \bmod p \] 即 \[ {2}^{ {2}^{ {2}^{ {.}^{ {.}^{ {.}^{2} } } } } } \bmod p \] 可以证明 \(a_n\bmod p\)在 \(n\) 足够大时为常数

多组数据 \(1\le Q\le 10^3\) ，\(1 \le p\le 10^7\)

其实这个题很简单

根据扩展欧拉定理，有 \[ \begin{aligned} a^b \equiv \begin{cases} a^b,&b< \varphi(m)\\\\ a^{b \ \bmod \ \varphi(m)+\varphi(m)},&b\ge \varphi(m) \end{cases} \pmod{m} \end{aligned} \] 显然当 \(n\) 足够大时，有 \(a_{n-1} > \varphi(p)\)

则 \[ a_{n}\bmod p = 2^{a_{n-1}\bmod\, \varphi(p)+\varphi(p)}\bmod p \] 可以发现原问题转化为了求解 \[ a_{n-1} \bmod \varphi(p) + \varphi(p) \] 递归处理即可

关于这个递归为什么是 \(O(\log p)\)

显然每一次递归 \(p\) 都会变成 \(\varphi(p)\)

根据欧拉函数的公式

设 \(n=\prod_{i=1}^{s}p_i^{k_i}\) \[ \varphi(n) = n \prod\limits_{i=1}^s\left(\dfrac{p_i-1}{p_i}\right) \] 观察函数，可以发现

• 当 \(n\) 为偶数时，一定会把 \(2\) 提出来变成 \(1\) ，也就是至少除以 \(2\)
• 当 \(n\) 为奇数时，一定会把一个素因子提出来变成一个偶数，也就是产生了 \(2\) 这个因子
• 重复以上的过程直到 \(n=1\) 结束

因此是 \(O(\log p)\) 的

所以总的时间复杂度为 \(O(Q\sqrt{p}\log p)\)

不用线性筛跑得反而快，因为 \(p\) 蛮大的，用了就变成 \(O(p+Q\log p)\) 了

数比较大，快速幂可能会爆了 \(\text{long long}\) ，所以要用龟速乘或者__int128

代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
int phi(int n)
{
    int ans=n;
    for(int i=2; i<=n/i; i++)
        if(n%i==0)
        {
            ans=ans/i*(i-1);
            while(n%i==0)n/=i;
        }
    if(n>1)ans=ans/n*(n-1);
    return ans;
}
int qpow(int a,int b,int p)
{
    int ans=1,base=a%p;
    while(b)
    {
        if(b&1)ans=(__int128)ans*base%p;
        base=(__int128)base*base%p;
        b>>=1;
    }
    return ans;
}
int solve(int p)
{
    if(p==1)return 0;
    return qpow(2,solve(phi(p))+phi(p),p);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int Q,p;
    cin >> Q;
    while(Q--)
    {
        cin >> p;
        cout << solve(p) << endl;
    }
    return 0;
}

用筛法求 \(\varphi(p)\) 跑了 1.52s，非筛法反倒就跑了114ms