快来和数论愉快玩♂耍啊23333

先证欧拉定理：若$(a,m)=1$，则$a^{\varphi(m)}\equiv1(\text{mod }m)$（证明来自《初等数论》）

取所有在$[1,m-1]$中与$m$互质的数$x_{1\cdots\varphi(m)}$，因为对$\forall i,j$有$x_i\not\equiv x_j(\text{mod }m)$，所以$ax_i\not\equiv ax_j(\text{mod }m)$，又因为$(ax_i,m)=1$，所以$x_{1\cdots n}$与$ax_{1\cdots n}$之间存在一一对应的模$m$同余关系

$\begin{align*}\prod\limits_{i=1}^{\varphi(m)}x_i\equiv\prod\limits_{i=1}^{\varphi(m)}ax_i\equiv a^{\varphi(m)}\prod\limits_{i=1}^{\varphi(m)}x_i(\text{mod }m)\end{align*}$

因为$(x_i,m)=1$，所以我们得到$a^{\varphi(m)}\equiv1(\text{mod }m)$

然后是所谓的“扩展欧拉定理”：若$x\geq\varphi(m)$，则$a^x\equiv a^{x\text{ mod }\varphi(m)+\varphi(m)}(\text{mod }m)$（证明来自）

一个要用到的引理是对任意质数$p$和$q\gt1$有$\varphi(p^q)\geq q$，用归纳法证明：对$q$归纳，假设$\varphi(p^q)\geq q$，那么$\varphi(p^{q+1})=p\varphi(p^q)\geq pq\geq q+1$

先证$m=p^q$的情况，其中$p$是质数

①若$(a,p)=1$，可直接用欧拉定理证明

②若$(a,p)=p$，那么$a=pt$，$a^x\equiv(pt)^x$，因为$x\geq \varphi(p^q)\geq q$，所以$a^x\equiv0(\text{mod }p^q)$，同理可得$a^{x\text{ mod }\varphi(m)+\varphi(m)}\equiv0(\text{mod }p^q)$

对于一般的$\begin{align*}m=\prod\limits_{i=1}^kp_k^{q_k}\end{align*}$，对每个$p_i^{q_i}$，我们都有$a^x\equiv a^{x\text{ mod }\varphi(p_i^{q_i})+\varphi(p_i^{q_i})}(\text{mod }p_i^{q_i})$

首先我们有$\varphi(p_i^{q_i})|\varphi(m)$，所以$a^{x\text{ mod }\varphi(m)+\varphi(m)}=a^{x+j\varphi(p_i^{q_i})}$，又有$a^{x\text{ mod }\varphi(p_i^{q_i})+\varphi(p_i^{q_i})}=a^{x+k\varphi(p_i^{q_i})}$，此时如果$p_i|a$，那么两个式子都模$p_i^{q_i}$余$0$，否则$(a,p_i)=1$，套用欧拉定理立得$a^{x\text{ mod }\varphi(p_i^{q_i})+\varphi(p_i^{q_i})}\equiv a^{x\text{ mod }\varphi(m)+\varphi(m)}(\text{mod }p_i^{q_i})$，即$a^x\equiv a^{x\text{ mod }\varphi(m)+\varphi(m)}(\text{mod }p_i^{q_i})$，直接合并所有质因数可以得到$a^x\equiv a^{x\text{ mod }\varphi(m)+\varphi(m)}(\text{mod }m)$，于是我们证明了扩展欧拉定理

然后来做这题，设$f(p)$表示题目中无限个$2$对$p$取模的值，那么$f(1)=0,f(p)\equiv2^{f(\varphi(p))+\varphi(p)}(\text{mod }p)$

然后就做完了（雾

#include
     
      typedef long long ll;const int T=10000000;int pr[10000010],phi[10000010];bool np[10000010];void sieve(){	int i,j,M;	M=0;	phi[1]=1;	for(i=2;i<=T;i++){		if(!np[i]){			M++;			pr[M]=i;			phi[i]=i-1;		}		for(j=1;j<=M;j++){			if(pr[j]*(ll)i>T)break;			np[i*pr[j]]=1;			if(i%pr[j]==0){				phi[i*pr[j]]=phi[i]*pr[j];				break;			}			phi[i*pr[j]]=phi[i]*(pr[j]-1);		}	}}int pow(int a,int b,int p){	int s=1;	while(b){		if(b&1)s=s*(ll)a%p;		a=a*(ll)a%p;		b>>=1;	}	return s;}int f(int p){	if(p==1)return 0;	return pow(2,f(phi[p])+phi[p],p);}int main(){	sieve();	int T,p;	scanf("%d",&T);	while(T--){		scanf("%d",&p);		printf("%d\n",f(p));	}}