嘘~ 正在从服务器偷取页面 . . .

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

发布日期: 2022-05-25

更新日期: 2022-07-22

文章字数: 596

洛谷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;
}