「bzoj3884」上帝与集合的正确用法 - 扩展欧拉定理

题目大意

    求无限个$2$：

$$2^{2^{2^{2^\cdots}}}\bmod p$$

    的值。

---

吐槽

个人觉得这道题是错题，虽然作为一道扩展欧拉定理的联系题来讲还是很不错的。

首先显然可知$2^{2^{2^{2^\cdots}}}$趋近于无穷，而无穷模一个数是无意义的。
证明如下：
假设无穷满足模的性质，则$+\infty\bmod x=y(y\lt x)$，因此$+\infty=kx+y$。
这显然是不现实的，故可知$+\infty$模一个数无意义。

以下将本题作为一道扩展欧拉定理的练习题讲述而不进行深究。

---

题目分析

根据扩展欧拉定理，当$x\ge\varphi(m)$：

$$a^x\equiv a^{x\bmod\varphi(m)+\varphi(m)}\pmod m$$

令$a=2,x=2^{2^{2^{\cdots}}}$，显然满足$x\ge\varphi(m)$。
因此可套用扩展欧拉定理得到：

$$2^{2^{2^{2^{\cdots}}}}\equiv2^{2^{2^{2^{\cdots}}}\bmod\varphi(m)+\varphi(m)}\pmod m$$

而我们发现$2^{2^{2^{\cdots}}}\bmod\varphi(m)$与$2^{2^{2^{\cdots}}}\bmod m$是同一种形式，因此可以递归。

而递归的过程耗时$O(\log m)$的，下面我们来证明这个时间复杂度。
引入一个结论：

对于任意一个正整数$x(x\gt2)$，满足$\varphi(x)$是偶数。

证明：
对$x$进行分解，$x=\prod_{i=1}^kp_i^{a_i}$，其中$p_i$是素数。
根据欧拉函数的计算式$\varphi(x)=x\prod_{i=1}^k\frac {p_i-1}{p_i}$（证明见这里），对$x$分类讨论。

• $x$是以$2$为底的幂$2^y$
  后半部分$\prod_{i=1}^k\frac {p_i-1}{p_i}=\frac12$，而$x$是$2^y(y\gt1)$，因此$\varphi(x)$是偶数。
• $x$不是$2^y$
  $x$必定存在一个$\gt2$的奇素数$p_i$。
  • 若$x$是奇数，则$\prod_{i=1}^k\frac {p_i-1}{p_i}$是偶数。
  • 若$x$是偶数，则$x$含有偶素数$2$，而$x$也含有$2$，两者抵消，所以$\varphi(x)$仍然是偶数。

Q.E.D.

我们再引入一个结论：

当$x$是偶数的时候，$\varphi(x)\le\frac x2$。

由$\varphi$的计算式显然。

因此，而若$x$是一个$\neq1$的奇数，$\varphi(x)$即是一个偶数。
故$x$经过$O(\log x)$次$x=\varphi(x)$的操作即可变为$1$。
时间复杂度证毕。

若每次暴力求欧拉函数，时间复杂度具体我也不会算，但一定比$O(\sqrt m\log m)$小。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

int Quick_Pow(int a,int b,int p) {
	int ans=1;
	for(; b; b>>=1,a=1ll*a*a%p)if(b&1)ans=1ll*ans*a%p;
	return ans;
}

int Phi(int x) {
	int sum=x;
	for(int i=2; i<=sqrt(x); i++)
		if(x%i==0) {
			sum=sum/i*(i-1);
			while(x%i==0)x/=i;
		}
	if(x>1)sum=sum/x*(x-1);
	return sum;
}

map<int,int> M;

int Cal(int p) {
	if(M.count(p))return M[p];
	int phi=Phi(p);
	return M[p]=Quick_Pow(2,Cal(phi)+phi,p);
}

int main() {
	int t=Get_Int();
	while(t--) {
		int p=Get_Int();
		printf("%d\n",Cal(p));
	}
	return 0;
}