P4139 上帝与集合的正确用法-白红宇

P4139 上帝与集合的正确用法

阅读量：2153 次

发布时间：2019-04-30

本文共 1142 字，大约阅读时间需要 3 分钟。

题目描述

一句话题意：

2^{2^{2^{2...}}} mod\ p

输入格式

第一行一个整数T，表示数据个数。

接下来T行，每行一个正整数p，代表你需要取模的值

输出格式

T行，每行一个正整数，为答案对p取模后的值

输入输出样例

输入

输出

说明/提示

对于100%的数据， $T\le 1000，p \le 10^7$

题解

扩展欧拉定理：

于是我们就可以照着上面的式子不断递归，m会逐渐变小，当m=1时就可退出递归。

我们会发现这题只会用上面的第二个式子，因为

b=2^{2^{2^{2...}}}

相当于无限，定大于

φ (m)

还要预处理出

φ

欧拉函数，参考。

且递归时求幂时要用快速幂，否则会炸。

代码

#include
   
    #include
    
     #define m 10000001#define ll unsigned long longusing namespace std;int phi[m],p[m>>3],pn,f[m],t,mp,modp;void Phi()//线性筛欧拉函数{
   	phi[1]=1;	for(int i=2; i<=m; i++)	{
   		if(!f[i])		{
   			p[++pn]=i;			phi[i]=i-1;		}		for(int j=1; j<=pn&&i*p[j]<=m; j++)		{
   			f[i*p[j]]=1;			if(i%p[j]==0)			{
   				phi[i*p[j]]=phi[i]*p[j];				break;			}			else phi[i*p[j]]=phi[i]*(p[j]-1);		}	}}int fpow(ll a,int b,int mod)//快速幂{
   	ll ans=1;	while(b)	{
   		if(b&1) ans=(ans*a)%mod;		a=(a*a)%mod;		b>>=1;	}	return ans;}int solve(ll mp){
   	if(mp==1) return 0;	return fpow(2,solve(phi[mp])+phi[mp],mp);}int main(){
   	Phi();	cin>>t;	for(int i=1; i<=t; i++)	{
   		cin>>modp;		cout<
     
      <