P4139 上帝与集合的正确用法

原题传送门

题意: T T T组数据,对于每个模数 p p p,求 2 2 2 . . . m o d 2^{2^{2^{...}}} mod 222...mod p p p, T ≤ 1 0 3 T\le 10^3 T≤103, p ≤ 1 0 7 p\le 10^7 p≤107

思路:扩展欧拉定理
显然 2 2 . . . {2^{2^{...}}} 22...这个无限数,是大于 φ ( p ) \varphi(p) φ(p)的,那么由扩展欧拉定理可得:
对于 b ≥ φ ( p ) b\ge \varphi(p) b≥φ(p),
有 a b ≡ a b   m o d   φ ( p ) + φ ( p )   m o d   p a^b\equiv a^{b\ mod\ \varphi(p)+\varphi(p)}\ mod\ p ab≡ab mod φ(p)+φ(p) mod p
很显然这个是递归式子,模数 φ ( p ) \varphi(p) φ(p)很快会降为 1 1 1,此时式子为 0 0 0
对于 φ ( p ) \varphi(p) φ(p),我们可以用线性筛预处理得到
时间复杂度: O ( p + T l o g   p ) O(p+Tlog\ p) O(p+Tlog p)

接下来我们谈一下,如何用线性筛预处理欧拉函数 φ ( x ) \varphi(x) φ(x)
对于 φ ( x ) \varphi(x) φ(x)我们利用如下性质:

  • φ ( x ) = x − 1 \varphi(x)=x-1 φ(x)=x−1, x ∈ p r i m e x\in prime x∈prime
  • φ ( x k ) = x k − x k − 1 \varphi(x^k)=x^k-x^{k-1} φ(xk)=xk−xk−1, x ∈ p r i m e x\in prime x∈prime
  • g c d ( m , n ) = 1 gcd(m,n)=1 gcd(m,n)=1, φ ( m n ) = φ ( m ) φ ( n ) \varphi(mn)=\varphi(m) \varphi(n) φ(mn)=φ(m)φ(n)

由此,我们得到欧拉函数是个积性函数,而线性筛可以预处理积性函数
Code

bool vis[N];
int cnt,prime[N/10],phi[N],p,t;
void get_phi(int n){
	phi[1]=1;
	for(int i=2;i<=n;i++){
		if(!vis[i]){
			prime[++cnt]=i;
			phi[i]=i-1;
		}
		for(int j=1;j<=cnt&&i*prime[j]<=n;j++){
			vis[i*prime[j]]=1;
			if(i%prime[j]==0){
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
			else phi[i*prime[j]]=phi[i]*(prime[j]-1);
		}
	}
}

套用这个模板,本题就很容易了
Code

#include <bits/stdc++.h>
using namespace std;
const int N=1e7+10;
typedef long long ll;
bool vis[N];
int cnt,prime[N/10],phi[N],p,t;
void get_phi(int n){
	phi[1]=1;
	for(int i=2;i<=n;i++){
		if(!vis[i]){
			prime[++cnt]=i;
			phi[i]=i-1;
		}
		for(int j=1;j<=cnt&&i*prime[j]<=n;j++){
			vis[i*prime[j]]=1;
			if(i%prime[j]==0){
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
			else phi[i*prime[j]]=phi[i]*(prime[j]-1);
		}
	}
}
int power(int a,int b,int p){
	int res=1;
	for(;b;b>>=1){
		if(b&1) res=1LL*res*a%p;
		a=1LL*a*a%p;
	}
	return res;
}
int solve(int x){
	if(x==1) return 0;
	return power(2,solve(phi[x])+phi[x],x);
}
int main(){
	get_phi(N);
	cin>>t;
	while(t--){
		cin>>p;
		cout<<solve(p)<<endl;
	}
	return 0;
}
上一篇:ssdb设置开启自启动


下一篇:c++使用easyx做出大飞机,手把手教你做游戏