天守阁的地板
题意即求：
\[\prod _ { i = 1 } ^ { n } \prod _ { j = 1 } ^ { n } \dfrac { \operatorname{lcm} ( i , j )} { i }\dfrac { \operatorname{lcm} ( i , j )} { j } \pmod {19260817} \]其中 \(T \le 10^3\)，\(n \le 10 ^ 6\)。
直接推导：
\[\begin{aligned} & \prod _ { i = 1 } ^ { n } \prod _ { j = 1 } ^ { n } \dfrac { \operatorname{lcm} ( i , j )} { i }\dfrac { \operatorname{lcm} ( i , j )} { j } \\ = & \prod _ { i = 1 } ^ { n } \prod _ { j = 1 } ^ { n } \dfrac { i j } { \gcd ( i , j ) ^ 2} \\ = & \prod _ { d = 1 } \prod _ { i = 1 } ^ { n } \prod _ { j = 1 } ^ { n } \left( \dfrac { i j } { d ^ 2} \right) ^ {\left[ \gcd ( i , j ) = d \right]} \\ = & \prod _ { d = 1 } \prod _ { i = 1 } ^ { \left\lfloor n / d \right\rfloor } \prod _ { j = 1 } ^ { \left\lfloor n / d \right\rfloor } \left( i j \right) ^ {\left[ \gcd ( i , j ) = 1 \right]} \\ = & \prod _ { d = 1 } \prod _ { i = 1 } ^ { \left\lfloor n / d \right\rfloor } \prod _ { j = 1 } ^ { \left\lfloor n / d \right\rfloor } \left( i j \right) ^ {\sum _ { k \mid i , k \mid j } \mu ( k )} \\ = & \prod _ { d = 1 } \prod _ { k =1 }\prod _ { i = 1 } ^ { \left\lfloor n / k d \right\rfloor } \prod _ { j = 1 } ^ { \left\lfloor n / k d \right\rfloor } \left( i j k ^ 2\right) ^ {\mu ( k )} \\ = & \prod _ { T = 1 } \prod _ { d \mid T }\prod _ { i = 1 } ^ { \left\lfloor n / T \right\rfloor } \prod _ { j = 1 } ^ { \left\lfloor n / T \right\rfloor } \left( i j d ^ 2\right) ^ {\mu ( d )} \\ = & \left (\prod _ { T = 1 } \prod _ { d \mid T }\prod _ { i = 1 } ^ { \left\lfloor n / T \right\rfloor } \prod _ { j = 1 } ^ { \left\lfloor n / T \right\rfloor } \left( i j\right) ^ {\mu ( d )} \right) \left (\prod _ { T = 1 } \prod _ { d \mid T }\prod _ { i = 1 } ^ { \left\lfloor n / T \right\rfloor } \prod _ { j = 1 } ^ { \left\lfloor n / T \right\rfloor } d ^ {2\mu ( d )} \right) \\ = & \left (\prod _ { T = 1 } \prod _ { i = 1 } ^ { \left\lfloor n / T \right\rfloor } \prod _ { j = 1 } ^ { \left\lfloor n / T \right\rfloor } \left( i j\right) ^ {\sum _ {d \mid T } \mu ( d )} \right) \left (\prod _ { T = 1 } \left( \prod _ { d \mid T } d ^ {2\mu ( d )} \right) ^ {\left\lfloor n / T \right\rfloor ^ 2 }\right) \\ = & \left (\prod _ { T = 1 } \prod _ { i = 1 } ^ { \left\lfloor n / T \right\rfloor } \prod _ { j = 1 } ^ { \left\lfloor n / T \right\rfloor } \left( i j\right) ^ {\left[ T = 1\right]} \right) \left (\prod _ { T = 1 } \left( \prod _ { d \mid T } d ^ {2\mu ( d )} \right) ^ {\left\lfloor n / T \right\rfloor ^ 2 }\right) \\ = & \left( n ! \right) ^ { 2 n } \left (\prod _ { T = 1 } \left( \prod _ { d \mid T } d ^ {2\mu ( d )} \right) ^ {\left\lfloor n / T \right\rfloor ^ 2 }\right) \end{aligned} \]预处理后，后面的那一部分整除分块即可。
时间复杂度 \(O( n \ln n + T \sqrt{ n } \log n)\)。
代码：
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
namespace Ehnaev{
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
return ret*f;
}
inline void write(ll x) {
static char buf[22];static ll len=-1;
if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
while(len>=0) putchar(buf[len--]);
}
}using Ehnaev::read;using Ehnaev::write;
inline void writeln(ll x) {write(x);putchar(10);}
const ll mo=19260817,N=1e6;
inline ll Qpow(ll b,ll p) {
ll r=1;while(p) {if(p&1) r=r*b%mo;b=b*b%mo;p>>=1;}return r;
}
ll T,n,cnt;
ll mu[N+5],prime[N+5],f[N+5],fc[N+5];
bool ff[N+5];
inline void Init() {
ff[1]=1;mu[1]=1;
for(ll i=2;i<=N;i++) {
if(!ff[i]) {prime[++cnt]=i;mu[i]=mo-1;}
for(ll j=1;j<=cnt&&i*prime[j]<=N;j++) {
ff[i*prime[j]]=1;
if(i%prime[j]==0) {
mu[i*prime[j]]=0;break;
}
mu[i*prime[j]]=mu[i]*mu[prime[j]]%mo;
}
}
fc[0]=1;f[0]=1;
for(ll i=1;i<=N;i++) {fc[i]=fc[i-1]*i%mo;f[i]=1;}
for(ll i=1;i<=N;i++) {
if(mu[i]==0) continue;
ll tmp=i*i%mo;ll invtmp=Qpow(tmp,mo-2);
for(ll j=i;j<=N;j+=i) {
if(mu[i]==mo-1) f[j]=f[j]*invtmp%mo;
else f[j]=f[j]*tmp%mo;
}
}
for(ll i=1;i<=N;i++) f[i]=f[i-1]*f[i]%mo;
}
int main() {
T=read();Init();
while(T--) {
n=read();ll ans=1;
for(ll i=1,j;i<=n;i=j+1) {
j=n/(n/i);
ll tmp=f[j]*Qpow(f[i-1],mo-2)%mo;
tmp=Qpow(tmp,(n/i)*(n/i)%(mo-1)+mo-1);
ans=ans*tmp%mo;
}
ans=ans*Qpow(fc[n],2*n)%mo;
writeln(ans);
}
return 0;
}