noteskey
怎么说，魔性的题目...拿来练手 min_25 正好...吧
首先就是把式子拆开来算贡献嘛
\]
for left
前面的东西我们发现可以转化...
\]
因为 \(\mu\) 只有在 i 每个质因子不超过 1 个的时候才有贡献，我们令 \(c(i)\) 表示 i 的质因子个数
\]
然后转指数相加
\]
然后我们令 \(S(n)\) 表示 \(c(i)\mu(i)\) 的前缀和，我们的任务就是求出 \(S(n)\) 了
我们发现这个东西不打好求，那么上万能的 min25 筛
假设我们已经求出了质数个数的前缀和函数 g ，那么我们设 \(S(i,j)\) 表示 i 以内 x 最小质因子大于等于 \(p_j\) 或者 x 为质数的\(\sum c(x)\mu(x)\)
那么转移就是：
\]
\]
其中 \(Mu(i,j)\) 表示 x 最小质因子大于等于 \(p_j\) 或者 x 为质数的 \(\sum \mu(x)\) 至于后面之所以要加上 j 就是考虑减去质数的重复贡献
然后边界条件就是 \(S(i,|P|)=-g(i),Mu(i,|P|)=-g(i)\)
然后让 ANS 初始为 \(2^{S(i,1)}\)
那么第一部分就已经完成了QVQ
for right
后面的东西还是可以推式子...
我们令 \(sum(n)\) 表示 \(\sum_{i=1}^n i\) ， \(h(n)\) 表示 \(\sum_{i=1}^{n} i[i∈Prime]\)
也就是说我们可以 min25 筛预处理出 h
然后我们想想怎么转移，我们知道 \(\sigma_{0}\) 是一个积性函数，也就是说我们枚举一个 质数 的 n 次方，那么它对答案的贡献不会受到别的因数的影响，所以我们考虑枚举质因子以及次数，那么答案就是
\]
\]
后面那个 \(g(p,e)\) 就是 \({{n\over p^e}-{n\over p^{e+1}}}\)
这里我们就是考虑 n 以内多少个数含有恰好 \(p^e\) 这个约数
那么转移就比较显然了...但是我们发现这里的 n 以内的质数有点多啊...
那么我们发现 e 可能大于 1 当且仅当 \(p^2<=n\) ，所以：
p^2<=n: 同上所述累乘贡献
p^2>n: 数论分块加速贡献累乘
于是这就是两部分贡献的计算了
但是有个比较突出的问题就是这道题的模数其实有两个，因为我们 min_25 中计算的数都是拿来当指数的，那么根据欧拉定理有 \(a^b=a^{b\%φ(p)+φ(p)} (mod ~p)\)（同余什么的就不来打了，麻烦）
那么这里的模数虽说是丧心病狂的大，但它是个质数，我们拿 \(p-1\) 带入做 \(φ(p)\) 就好了
然后就是一些小细节的问题了...
code
代码中有详细解释...
//by Judge
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define Rg register
#define fp(i,a,b) for(Rg int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(Rg int i=(a),I=(b)-1;i>I;--i)
#define db long double
#define ll long long
using namespace std;
const ll mod=1e12+39,P=mod-1;
const int M=1e6+3;
typedef int arr[M];
typedef ll ARR[M];
#ifndef Judge
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
char buf[1<<21],*p1=buf,*p2=buf;
inline ll read(){ ll x=0,f=1; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;
} char sr[1<<21],z[20];int CCF=-1,Z;
inline void Ot(){fwrite(sr,1,CCF+1,stdout),CCF=-1;}
inline void print(ll x,char chr='\n'){
if(CCF>1<<20)Ot();if(x<0)sr[++CCF]=45,x=-x;
while(z[++Z]=x%10+48,x/=10);
while(sr[++CCF]=z[Z],--Z);sr[++CCF]=chr;
} ll n,m,cnt,tot,sq,ans; arr id1,id2,v,p; ARR w,g,h,f,sp,sum;
namespace calc{
inline ll add1(Rg ll x,Rg ll y){return x+y>=mod?x+y-mod:x+y;}
inline ll add2(Rg ll x,Rg ll y){return x+y>=P?x+y-P:x+y;}
inline ll mul1(Rg ll x,Rg ll y){return x*y-(ll)((db)x*y/mod)*mod;}
inline ll mul2(Rg ll x,Rg ll y){return x*y-(ll)((db)x*y/P)*P;}
inline ll dec1(Rg ll x,Rg ll y){return x-y<0?x-y+mod:x-y;}
inline ll dec2(Rg ll x,Rg ll y){return x-y<0?x-y+P:x-y;}
inline ll Sum(Rg ll x){return x&1?mul2(x,(x+1)>>1):mul2(x>>1,x+1);}
inline ll qpow(Rg ll x,Rg ll p){ p=(p%P+P)%P; Rg ll s=1;
for(;p;p>>=1,x=mul1(x,x)) if(p&1) s=mul1(s,x); return s;
}
} using namespace calc;
inline void prep(int n){
fp(i,2,n){ if(!v[i]) p[++cnt]=i,sp[cnt]=sp[cnt-1]+i;
for(Rg int j=1;j<=cnt&&i*p[j]<=n;++j)
{v[i*p[j]]=1; if(!(i%p[j])) break;}
}
}
inline int ID(Rg ll x){return x<=sq?id1[x]:id2[n/x];}
inline void Min_25(ll n){ m=0,sq=sqrt(n),
tot=upper_bound(p+1,p+1+cnt,sq)-1-p;
for(ll i=1;i<=n;i=w[m]+1) w[++m]=n/(n/i),g[m]=w[m]-1,
sum[m]=h[m]=Sum(w[m]),h[m]=dec2(h[m],1),
w[m]<=sq?id1[w[m]]=m:id2[n/w[m]]=m;
fp(j,1,tot) for(Rg int i=m,k;1ll*p[j]*p[j]<=w[i];--i)
k=ID(w[i]/p[j]),g[i]=dec2(g[i],dec2(g[k],j-1)), // g 为质数个数前缀和
h[i]=dec2(h[i],mul2(p[j],dec2(h[k],sp[j-1]))); // h 为质数前缀和
fp(i,1,m) f[i]=g[i]=dec2(0,g[i]); // 初始化 f g
fd(j,tot,1) for(Rg int i=m,k;1ll*p[j]*p[j]<=w[i];--i)
k=ID(w[i]/p[j]),g[i]=dec2(g[i],add2(g[k],j)), // mu 也要求出前缀和
f[i]=dec2(f[i],add2(add2(g[k],j),add2(f[k],j))); //计算所求函数的前缀和
ans=qpow(2,f[m]); Rg ll i,j,res;
/////////////////////////////part 2///////////////////////////////////
for(j=1;j<=tot&&1ll*p[j]*p[j]<=n;++j){ //对于 p_i <= sqrt(n) 每次枚举质数个数算贡献
Rg ll x=p[j],y=1ll*p[j]*p[j];
for(i=1;x<=n;++i,x=y,y*=p[j])
res=dec2(mul2(x,sum[ID(n/x)]),y<=n?mul2(y,sum[ID(n/y)]):0),
ans=mul1(ans,qpow(i+1,res));
}
i=p[j-1]+1,j=n/(n/i);
for(;i<=j;++i) if(!v[i]) ans=mul1(ans,qpow(2,mul2(i,n/i)));
for(;i<=n;i=j+1) j=n/(n/i),res=dec2(h[ID(j)],h[ID(i-1)]), //对于 p_i > sqrt(n) 数论分块算贡献
res=mul2(res,sum[ID(n/i)]),ans=mul1(ans,qpow(2,res));
print(ans);
}
int main(){ int T=read(); prep(1e6);
while(T--) n=read(),Min_25(n); return Ot(),0;
}