bzoj3884: 上帝与集合的正确用法 欧拉降幂

#include <bits/stdc++.h>
#define ll long long 
using namespace std;
ll euler(ll x){
	ll ans = x;
	for(ll i=2;i*i<=x;i++){
		if(x%i==0){
			ans-=ans/i;
			while(x%i==0){
				x/=i;
			}
		}
	}
	if(x>1)ans-=ans/x;
	return ans;
}
ll quick(ll x,ll y,ll mo){
	ll ans = 1;
	while(y){
		if(y&1)ans=ans*x%mo;
		y>>=1;
		x=x*x%mo;
	}
	return ans;
}

ll fu(ll p){
	if(p==1)return 0;
	ll temp = 0;
	while(~p&1) p>>=1,temp++;
	ll ph = euler(p);
	ll re = fu(ph);
	re+=(ph - temp%ph);
	re%=ph;
	re = quick(2,re,p)%p;
	return re<<temp; 
}

int main(){	
	ll t;
	cin>>t;
	while(t--){
		ll tp;	cin>>tp;
		cout<<fu(tp)<<endl;
	}
}
/*

*/