返回首页 返回专题

【BZOJ3884】上帝与集合的正确用法 题解

其实我觉得这题的任何推导都是错误的，一个数不断自己乘自己，它模p的值是会永无止境地变化下去的，不可能到了什么时候变成一个定值。所以这里的无穷个，我觉得定义上有疑义

不过既然他出了这题，我们就还是好好推导一下

首先，拓展欧拉定理中，有一条是这样说的：

设a=2，n=2^2^2^2^…，则n必然满足前提条件，于是在这个假设条件下，定理成立。

利用这个柿子来画出更大的柿子：

注意，由于n的定义是无穷的，因此可以随便添上2

这样我们就得到了一个递归式。

可以直接递归求解了吗？

当然可以！边界条件呢？

我们知道，任何整数对1取模都等于0，因此当p=1时可以直接返回0

然后就可以愉快地搞一个快速幂，再求一个欧拉函数，就解决了本题！求欧拉函数别用线性筛，太慢！暴力O(sqrt(p))地求就可以了，快到飞起

#include<bits/stdc++.h>
using namespace std;

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

int GetPhi(int n)
{
	int res=n;
	for(int i=2;i*i<=n;i++)
	{
		if(n%i==0) res-=res/i;
		while(n%i==0) n/=i;
	}
	if(n>1) res-=res/n;
	return res;
}

int F(int p)
{
	if(p==1) return 0;
	int phi=GetPhi(p);
	return QuickPow(2,F(phi)+phi,p);
}

int main()
{
	int T,p;
	for(cin>>T;T;T--)
	{
		scanf("%d",&p);
		printf("%d\n",F(p));
	}
	return 0;
}