【BZOJ3884】上帝与集合的正确用法（欧拉定理）【第500篇随笔祭】

点此看题面

大致题意： 求\(2^{2^{2^{...}}}(mod\ p)\)。

扩展欧拉定理

根据扩展欧拉定理，当\(b\ge\phi(p)\)时，\(a^b\equiv a^{b\ mod\ \phi(p)+\phi(p)}(mod\ p)\)。

对于此题，我们设\(f(p)=2^{2^{2^{...}}}(mod\ p)\)，代入扩展欧拉定理就有：

由此我们只要递归就能求出答案。

其中递归的边界为\(p\le2\)时\(f(p)=0\)。

代码

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
using namespace std;
class LinearSieve
{
	private:
		#define S 10000000
		int Pt,P[S+5],phi[S+5];
	public:
		I int operator [] (CI x) Con {return phi[x];}
		I LinearSieve()//欧拉筛筛φ
		{
			phi[1]=1;for(RI i=2,j,t;i<=S;++i)
				for(!P[i]&&(phi[P[++Pt]=i]=i-1),j=1;j<=Pt&&(t=i*P[j])<=S;++j)
					if(P[t]=1,i%P[j]) phi[t]=phi[i]*(P[j]-1);else {phi[t]=phi[i]*P[j];break;}
		}
}Phi;
I int QP(RI x,RI y,RI X) {RI t=1;W(y) y&1&&(t=1LL*t*x%X),x=1LL*x*x%X,y>>=1;return t;}//快速幂
I int f(CI X) {return X<=2?0:QP(2,f(Phi[X])+Phi[X],X);}//递归求f
int main()
{
	RI Tt,X;scanf("%d",&Tt);W(Tt--) scanf("%d",&X),printf("%d\n",f(X));return 0;
}

【BZOJ3884】上帝与集合的正确用法（欧拉定理）【第500篇随笔祭】

原文：https://www.cnblogs.com/chenxiaoran666/p/BZOJ3884.html