快来和数论愉快玩♂耍啊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<stdio.h>
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));
}
}