bzoj 3884 上帝与集合的正确用法

Posted on | Views:

拓展欧拉定理.

拓展欧拉定理 $a^b\equiv a^{b\bmod \varphi(p)+\varphi(p)} \bmod p$ ,并不要求 $b$ 与 $p$ 互质.

则 $2^{2^{2^{\dots}}}\equiv (2)^{2^{2^{2^{\dots}}}}\equiv (2)^{2^{2^{2^{\dots}}}\bmod \varphi(p)+\varphi(p)}\bmod p$ .

求出 $\varphi(p)$ 后递归求解,边界是当 $p=1$ 时,答案为 $0$ .

打表发现,对于 $10^7$ 之内的任何 $p$ ,最多递归 $3$ 次后就会变成 $1$ ,这样做速度是有保证的.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e7+1;
int mul(int a,int b,int P)
{
	return 1LL * a * b % P;
}
int fpow(int a,int b,int P)
{
	int res=1;
	while(b)
	{
		if(b&1)
			res=mul(res,a,P);
		a=mul(a,a,P);
		b>>=1;
	}
	return res;
}
int getphi(int x)
{
	int res=x;
	for(int i=2;i*i<=x;++i)
		if(x%i==0)
		{
			res/=i;
			res*=(i-1);
			while(x%i==0)		
				x/=i;
		}
	if(x!=1)
		res/=x,res*=(x-1);
	return res;
}
int calc(int p)
{
	if(p==1)
		return 0;
	int x=getphi(p);
	return fpow(2,calc(x)+x,p);
}
/*int prime[MAXN],cnt=0,phi[MAXN],f[MAXN],ism[MAXN];
void init(int n)
{
	int ans=0;
	f[1]=0;
	phi[1]=ism[1]=1;
	for(int i=2;i<=n;++i)
	{
		f[i]=f[phi[i]]+1;
		ans=max(ans,f[i]);
		if(!ism[i])
		{
			prime[++cnt]=i;
			phi[i]=i-1;
		}
		for(int j=1;j<=cnt && n/i>=prime[j];++j)
		{
			int x=prime[j]*i;
			if(i%prime[j]==0)
			{
				phi[x]=phi[i]*prime[j];
				break;
			}
			phi[x]=phi[i]*(j-1);
		}
	}
	cout<<ans<<endl;
}*/
int main()
{
//	init(MAXN-1);
	int T=read();
	while(T--)
	{
		int p=read();
		int ans=calc(p);
		printf("%d\n",ans);
	}
	return 0;
}