Give Candies //欧拉函数模板 快速幂模板 欧拉降幂模板 (ACM-ICPC 2018 焦作赛区网络预赛)
求 2^n n<=10^100000 直接万能欧拉降幂
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define LL long long
LL Euler(LL nqn){
LL ret=nqn;
for(LL i=2;i<=sqrt(nqn);i++)
if(nqn%i==0){
ret=ret/i*(i-1);//先进行除法防止溢出(ret=ret*(1-1/p(i)))
while(nqn%i==0)
nqn/=i;
}
if(nqn>1)
ret=ret/nqn*(nqn-1);
return ret;
}
LL quick_mod(LL aqa,LL nqn,LL mood){
LL ret=1;aqa=aqa%mood;
while(nqn){
if(nqn&1){
ret=(ret*aqa)%mood;
}
aqa=(aqa*aqa)%mood;
nqn=nqn>>1;
}
return ret;
}
LL string_quick_mod(LL aqa,char sqs[],LL mood){ //欧拉万能降幂
int len=strlen(sqs);
LL ola=Euler(mood);
LL nqn=0;
int i;
for(i=0;i<len;++i){
nqn=(nqn*10+sqs[i]-'0');
if(nqn>=ola) {
break;
}
}
if(i==len) return quick_mod(aqa,nqn,mood);//第二种情况
nqn=0;
for(int i=0;i<len;++i){
nqn=(nqn*10+sqs[i]-'0')%ola;
}
return quick_mod(aqa,nqn+ola,mood); //第三种情况
}
int main(){
ios :: sync_with_stdio(false);
int T;char s[100005];
cin>>T;
LL inv=quick_mod(2,mod-2,mod); //费马小定理
while(T--){
cin>>s;
cout<<string_quick_mod(2,s,mod)*inv%mod<<endl;
}
return 0;
}