Description：

求： $$ \prod_{i=1}^n\sigma_0(i)^{\mu(i)+i} $$ $1\leqslant n\leqslant 10^{11}$

Solution：

首先把式子分成两部分： $$ ans=\prod_{i=1}^n\sigma_0(i)^i\prod_{i=1}^n\sigma_0(i)^{\mu(i)} $$ 先计算前面那部分， $\sigma_0$ 是积性函数，那么 $\sigma_0^k$ 也是积性函数，那就可以把每个质因子分开计算也就是： $$ ans=\prod_{i=1}^n\prod_{j=1}^{|p|}(q_j+1)^k=\prod_{i=1}^{|p|}\prod_{k=1}^{p_i^k\leqslant n}(k+1)^{p_i^k\times S(\lfloor\frac n {p_i^k}\rfloor)-p_i^{k+1}\times S\lfloor(\frac n{p_i^{k+1}}\rfloor)} $$ 其中： $$ S(n)=\sum_{i=1}^ni $$ 但是这样由于 $p$ 有 $O(\frac n{\ln n})$ 个，所以复杂度还是过不去的，这时候一个很神奇的转化是把 $p$ 按和 $\sqrt n$ 的大小关系分类，其实这也是一个常用套路，因为合数一定存在一个 $\leqslant \sqrt n$ 的质因数，超过 $\sqrt n$ 的质因数最多只有 $1$ 个，这时会发现超过 $\sqrt n$ 的质因数的指数一定是 $1$ ，于是： $$ \begin{align} ans=&\prod_{p\leqslant \sqrt n}\prod_{k=1}^{p^k\leqslant n}(k+1)^{p^k\times S(\lfloor\frac n {p^k}\rfloor)-p^{k+1}\times S\lfloor(\frac n{p^{k+1}}\rfloor)}\times\prod_{p>\sqrt n}2^{p\times S(\lfloor\frac n p\rfloor)}\\ =&\prod_{p\leqslant \sqrt n}\prod_{k=1}^{p^k\leqslant n}(k+1)^{p^k\times S(\lfloor\frac n {p^k}\rfloor)-p^{k+1}\times S\lfloor(\frac n{p^{k+1}}\rfloor)}\times2^{\sum_{p=\sqrt n+1}^n[p\ is\ prime]p\times S(\lfloor\frac n p\rfloor)}\\ \end{align} $$ 前面那部分直接求就好了，时间复杂度 $O(\sqrt n\log n)$ ，后面那部分可以 $\min\_25$ 筛求质数个数 $+$ 除法分块，复杂度之所以是对的是因为就像杜教筛 $+$ 除法分块那样实际上都是求的所有 $x=\lfloor\frac n i\rfloor$ 时的值，所以只用最开始做一遍 $\min\_25$ 筛即可，复杂度 $O(n\sqrt n+\frac{n^{\frac 3 4}}{\log n})$ 。

然后再考虑第二部分，由于当 $i$ 有一个质因子次数大于 $2$ 时 $\mu(i)=0$ ，因此可以设 $d(i)$ 表示 $i$ 的素因子个数： $$ ans=\prod_{i=1}^n\sigma_0(i)^{\mu(i)}=\prod_{i=1}^n2^{d(i)\mu(i)}=2^{\sum_{i=1}^nd(i)\mu(i)} $$ 这个时候我们可以强上 $\min\_25$ 筛，也就是设： $$ \begin{align} f(n,j)&=\sum_{i=1}^n[n\ is\ prime\ or\ minp(i)\geqslant p_j]\mu(i)\times d(i)\\ f1(n,j)&=\sum_{i=1}^n[n\ is\ prime\ or\ minp(i)\geqslant p_j]\mu(i) \end{align} $$ 然后套用 $\min\_25$ 筛从大往小转移，因为当 $n$ 含有多个相同的质因数时贡献为零，因此只用展开一层，那么转移为： $$ \begin{align} f1(n,j)&=f1(n,j+1)+(-1)\times (f1(\lfloor\frac n{p_j}\rfloor,j+1)-f1(p_j,j+1))\\ f(n,j)&=f(n,j + 1)+(-1)\Bigl((f1(\lfloor\frac n {p_j}\rfloor,j+1)+f(\lfloor\frac n {p_j}\rfloor,j+1))-(f1(p_j,j+1)-f(p_j,j+1))\Bigr) \end{align} $$ 第一个转移的含义是后面应该加上最小质因子为 $p_j$ 的数，由于 $\mu$ 是积性的所以可以提出来一个 $-1$ ，然后质数被多次计算了要减掉。第二个转移的含义类似，但是由于 $d(i)$ 都会加一所以应该加上 $f1$ 。

边界为 $f1(k,|p|)=f(k,|p|)=-[1,k]$ 素数个数。

$f1(p_j,j+1)=f(p_j,j+1)=-[1,p_j]$ 素数个数 $=j$ 。

然后最后 $f(n,1)$ 就是要求的。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<cctype>

#include<cstring>

using namespace std;

typedef long long ll;

ll n;

#define MAXN 1000010

ll N;

#define MOD 1000000000039ll

#define PHI 1000000000038ll

#define I inline

#define R register

I ll Mul(ll a,ll b,ll p)

{

	return ((a * b - (ll)(((long double)a * b + 0.5) / p) * p) % p + p) % p;

}

bool isprime[MAXN];

int prime[MAXN],tot = 0;

ll ps[MAXN];

I void sieve(int n)

{

	for(R int i = 2;i <= N;++i)isprime[i] = true;

	for(R int i = 2;i <= N;++i)

	{

		if(isprime[i])

		{

			prime[++tot] = i;

			ps[tot] = (ps[tot - 1] + i) % PHI;

		}

		for(R int j = 1;j <= tot && i * prime[j] <= N;++j)

		{

			isprime[i * prime[j]] = false;

			if(i % prime[j] == 0)break;

		}

	}

	return;

}

I ll S(ll n,ll p)

{

	if(n % 2 == 0)return Mul(n / 2,n + 1,p);

	else return Mul((n + 1) / 2,n,p);

}

I ll power(ll a,ll b,ll p)

{

	R ll res = 1;

	while(b > 0)

	{

		if(b & 1)res = Mul(res,a,p);

		a = Mul(a,a,p);

		b = b >> 1;

	}

	return res;

}

namespace SOLVE1

{

	int id1[MAXN],id2[MAXN];

	ll w[MAXN];

	int m;

	I int& id(ll k){return (k <= N ? id1[k] : id2[n / k]);}

	ll g[MAXN];

	I ll solve1(ll n)

	{

		R ll sum = 0;

		m = 0;

		for(R ll l = 1,r;l <= n;l = r + 1)

		{

			r = n / (n / l);

			w[++m] = n / l;

			id(n / l) = m;

			g[m] = S(w[m],PHI) - 1;

		}

		for(R int j = 1;j <= tot;++j)

		{

			for(R int i = 1;i <= m && 1ll * prime[j] * prime[j] <= w[i];++i)

			{

				g[i] = (g[i] - Mul(prime[j],(g[id(w[i] / prime[j])] - ps[j - 1] + PHI) % PHI,PHI)) % PHI;

				if(g[i] < 0)g[i] += PHI;

			}

		}

		for(R ll l = N + 1,r;l <= n;l = r + 1)

		{

			r = n / (n / l);

			sum = (sum + Mul((g[id(r)] - g[id(l - 1)] + PHI) % PHI,S(n / l,PHI),PHI)) % PHI;

		}

		R ll res2 = power(2,sum,MOD);

		R ll res1 = 1;

		R int i;

		for(i = 1;1ll * prime[i] * prime[i] <= n && i <= tot;++i)

		{

			R ll p = prime[i];

			for(R int k = 1;p <= n;p *= prime[i],++k)

			{

				R ll w = (Mul(p % PHI,S(n / p,PHI),PHI) - Mul(p * prime[i] % PHI,S(n / (p * prime[i]),PHI),PHI) + PHI) % PHI;

				res1 = Mul(res1,power(k + 1,w,MOD),MOD);

			}

		}

		return Mul(res1,res2,MOD);

	}

}

namespace PCNT

{

	int id1[MAXN],id2[MAXN];

	ll w[MAXN];

	int m;

	I int id(ll k){return (k <= N ? id1[k] : id2[n / k]);}

	ll g[MAXN];

	I ll calc(ll n)

	{

		if(n <= 1)return 0;

		m = 0;

		for(R ll l = 1,r;l <= n;l = r + 1)

		{

			r = n / (n / l);

			w[++m] = n / l;

			if(w[m] <= N)id1[w[m]] = m;

			else id2[n / w[m]] = m;

			g[m] = w[m] - 1;

		}

		for(R int j = 1;j <= tot;++j)

		{

			for(R int i = 1;i <= m && 1ll * prime[j] * prime[j] <= w[i];++i)

			{

				g[i] = (g[i] - (g[id(w[i] / prime[j])] - j + 1)) % PHI;

				if(g[i] < 0)g[i] += PHI;

			}

		}

		return g[id(n)];

	}

}

namespace SOLVE2

{

	int id1[MAXN],id2[MAXN];

	ll w[MAXN];

	int m = 0;

	I int id(ll k){return (k <= N ? id1[k] : id2[n / k]);}

	ll f1[MAXN],f[MAXN];

	I ll solve2(ll n)

	{

		m = 0;

		PCNT::calc(n);

		for(R ll l = 1,r;l <= n;l = r + 1)

		{

			r = n / (n / l);

			w[++m] = n / l;

			if(w[m] <= N)id1[w[m]] = m;

			else id2[n / w[m]] = m;

			f1[m] = PHI - PCNT::g[PCNT::id(w[m])];

			f[m] = PHI - PCNT::g[PCNT::id(w[m])];

		}

		for(R int j = tot;j >= 1;--j)

		{

			for(R int i = 1;i <= m && 1ll * prime[j] * prime[j] <= w[i];++i)

			{

				R int k = id(w[i] / prime[j]);

				f1[i] = (f1[i] - f1[k] - j) % PHI;if(f1[i] < 0)f1[i] += PHI;

				f[i] = (f[i] - f[k] - f1[k] - 2 * j) % PHI;if(f[i] < 0)f[i] += PHI;

			}

		}

		return power(2,f[id(n)],MOD);

	}

}

void work()

{

	//init();

	scanf("%lld",&n);

	tot = 0;

	sieve(N = sqrt(n));

	R ll ans2 = SOLVE2::solve2(n);

	R ll ans1 = SOLVE1::solve1(n);

	cout << Mul(ans1,ans2,MOD) << endl;

	return;

}

int main()

{

	int testcases;

	scanf("%d",&testcases);

	while(testcases--)work();

	return 0;

}