Description：

求： $$ \prod_{i=1}^n\prod_{j=1}^n\frac{\text{lcm}(i,j)}i\times\frac{\text{lcm}(i,j)}{j} $$ $1\leqslant n\leqslant 10^6$

Solution：

$$ \begin{align}原式&=\prod_{i=1}^n\prod_{j=1}^n\frac{ij}{\gcd(i,j)^2}\\&=(n!)^{2n}\biggl(\frac1{\begin{align}\prod_{i=1}^n\prod_{j=1}^n\gcd(i,j)\end{align}}\biggr)^2\end{align} $$

所以重点变成了求： $$ \prod_{i=1}^n\prod_{j=1}^n\gcd(i,j) $$ 按照套路，在最外层枚举一个 $\gcd$ ，即： $$ \prod_{d=1}^nd^{\begin{align}\sum_{i=1}^{\lfloor \frac nd\rfloor}\sum_{j=1}^{\lfloor\frac nd\rfloor}[\gcd(i,j)=1]\end{align}} $$ 所以重点又变成求： $$ \sum_{i=1}^{\lfloor \frac nd\rfloor}\sum_{j=1}^{\lfloor\frac nd\rfloor}[\gcd(i,j)=1] $$ 可以反演，但是反演化成 $\mu$ 了我也只会 $O(n\sqrt n+T\sqrt n\log n)$ 的复杂度。

其实观察一下上面那个式子，非常像仪仗队那道题，也就是说上式等价于： $$ \sum_{i=1}^n\varphi(i)\times 2-1 $$ 于是线性筛一个 $\varphi$ 的前缀和在里层用快速幂计算就可以获得 $O(n+T\sqrt n\log n)$ 的复杂度了，注意指数不能乱模。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MAXN 1000010

int prime[MAXN],tot = 0;

bool isprime[MAXN];

int phi[MAXN];

long long sum[MAXN];

long long f[MAXN];

int fac[MAXN],inv[MAXN];

#define MOD 19260817

int power(int a,long long b)

{

    int res = 1;

    while(b > 0)

    {

        if(b & 1)res = 1ll * res * a % MOD;

        a = 1ll * a * a % MOD;

        b = b >> 1;

    }

    return res;

}

void sieve()

{

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

    sum[1] = phi[1] = 1;

    for(int i = 2;i < MAXN;++i)

    {

        if(isprime[i])

        {

            prime[++tot] = i;

            phi[i] = i - 1;

        }

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

        {

            int k = i * prime[j];

            isprime[k] = false;

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

            {

                phi[k] = phi[i] * prime[j];

                break;

            }

            else

            {

                phi[k] = phi[i] * phi[prime[j]];

            }

        }

        sum[i] = sum[i - 1] + phi[i];

    }

    for(register int i = 1;i < MAXN;++i)

    {

        f[i] = sum[i] * 2 - 1;

    }

    fac[0] = 1;

    for(int i = 1;i < MAXN;++i)fac[i] = 1ll * fac[i - 1] * i % MOD;

    inv[0] = 1;

    for(int i = 1;i < MAXN;++i)inv[i] = power(fac[i],MOD - 2);

    return;

}

void work()

{

    int n;

    scanf("%d",&n);

    int res = 1;

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

    {

        r = n / (n / l);

        res = 1ll * res * power(1ll * fac[r] * inv[l - 1] % MOD,f[n / l]) % MOD;

    }

    printf("%lld\n",1ll * power(fac[n],2 * n) * power(1ll * res * res % MOD,MOD - 2) % MOD);

    return;

}

int main()

{

    sieve();

    int testcases;

    scanf("%d",&testcases);

    while(testcases--)work();

    return 0;

}