这是 luogu P4917 的题解，只是为了方便放学习笔记里就把这篇搬过来了。QWQ
正文
首先分析题意，明显可以发现的是，如果想使最后摆成一个正方形，且用的地板最小，那这个正方形的边长就是 \(\operatorname{lcm}(a,b)\)，那地板的数量就是 \(\frac{\operatorname{lcm}(a,b)}{a}\times \frac{\operatorname{lcm}(a,b)}{b}\)。
现在开始推柿子。
求：
\[\prod\limits_{i=1}^n\prod\limits_{j=1}^n\frac{\operatorname{lcm}^2(i,j)}{ij} \bmod19260817 \]首先知道 \(\operatorname{lcm}(a,b)=\frac{ab}{\gcd(a,b)}\)。
\[\prod\limits_{i=1}^n\prod\limits_{j=1}^n\frac{ij}{\gcd^2(i,j)}\bmod19260817 \]\[\frac{\prod\limits_{i=1}^n\prod\limits_{j=1}^nij}{(\prod\limits_{i=1}^n\prod\limits_{j=1}^n\gcd(i,j))^2}\bmod 19260817 \]先看分子。
\[\prod\limits_{i=1}^n\prod\limits_{j=1}^nij \]\[\prod\limits_{i=1}^ni^nn! \]\[(n!)^n(n!)^n \]\[(n!)^{2n} \]因为这是分子，所以计算是直接对 \(19260817\) 就行了。
再看分母。
\[\prod\limits_{i=1}^n\prod\limits_{j=1}^n\gcd(i,j) \]（那个平方等最后直接乘就行了）
\[\prod\limits_{i=1}^n\prod\limits_{j=1}^n\sum\limits_{d=1}^nd[\gcd(i,j)=d] \]显然，对于任一个 \(i\) 和 \(j\)，\(\gcd(i,j)\) 有唯一确定的值，且 \([...]\) 里东西如果为假就为 \(0\)，所以就用的是求和。
\[\prod\limits_{d=1}^n\prod\limits_{i=1}^n\prod\limits_{j=1}^nd[\gcd(\frac{i}{d},\frac{j}{d})=1][d|i][d|j] \]\[\prod\limits_{d=1}^n\prod\limits_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\prod\limits_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}d[\gcd(i,j)=1] \]为方便，设 \(m=\left\lfloor\frac{n}{d}\right\rfloor\)。
\[\prod\limits_{d=1}^nd^{\sum\limits_{i=1}^m\sum\limits_{j=1}^m[\gcd(i,j)=1]} \]只看指数。
\[\sum\limits_{i=1}^m\sum\limits_{j=1}^m[\gcd(i,j)] \]可以发现这和仪仗队里的柿子一模一样，但我还是小推一下。
\[2\times\sum\limits_{i=1}^m\sum\limits_{j=1}^i[\gcd(i,j)=1]-1 \]\[2\times\sum\limits_{i=1}^m\varphi(i)-1 \]再看：
\[d^{2\times\sum\limits_{i=1}^m\varphi(i)-1} \bmod 19260817 \]知道 \(a^{p-1} \equiv 1\pmod p\)（\(p\) 为质数且 \(\gcd(a,p)=1\)）（费马小定理）。
相当于当我们求 \(2\times\sum\limits_{i=1}^n\varphi(i)-1\) 时，我们可以将其对 \(19260816\)（\(19260817-1\)）取余，这样我们提前求的时候就不怕爆 long long 了。QWQ
所以我们要求的就变成了:
\[\prod\limits_{d=1}^nd^{f(\left\lfloor\frac{n}{d}\right\rfloor)} \bmod 19260817 \]（\(f(x)=2\times\sum\limits_{i=1}^x\varphi(i)-1\)）
如果暴力求，时间复杂度会爆炸，所以考虑优化。显然可以用数论分块优化，对于枚举的 \(\left\lfloor\frac{n}{d}\right\rfloor\)，它的贡献为 \((\frac{r!}{(l-1)!})^{f(\left\lfloor\frac{n}{d}\right\rfloor)}\)，所以可以再套一个快速幂即可。
再往回看，现在整体的柿子就变成了：
\[\frac{(n!)^{2n}}{(\prod\limits_{d=1}^nd^{f(\left\lfloor\frac{n}{d}\right\rfloor)})^2} \bmod 19260817 \]所以分别求出分子和分母，记得将分母变成平方并转成逆元即可。
代码
点击查看代码
#include<bits/stdc++.h>
#define XD 114514
#define MAXN 1000010
#define ll long long
using namespace std;
const int mod=19260817;
const int mod2=19260816;//mod-1
int t,n,ans,ans1,ans2;
int fac[MAXN],phi[MAXN],num[MAXN];
//num 为欧拉函数前缀和，fac 为阶乘
vector<int> prm;
bool vis[MAXN];
void sieve(){
phi[1]=num[1]=1;
for(int i=2;i<=1e6;i++){
if(!vis[i]) prm.push_back(i),phi[i]=i-1;
num[i]=(num[i-1]+phi[i])%mod2;
for(auto j:prm){
if(i*j>1e6) break;
vis[i*j]=true;
if(i%j==0){
phi[i*j]=phi[i]*j;break;
}
phi[i*j]=phi[i]*phi[j];
}
}
fac[0]=1;
for(int i=1;i<=1e6;i++) fac[i]=1ll*fac[i-1]*i%mod;
}
int power(int x,int y){//快速幂
int nem=1;
while(y){
if(y&1) nem=1ll*nem*x%mod;
x=1ll*x*x%mod;y>>=1;
}
return nem;
}
int inv(int x){//求逆元
if(x==0 or x==1) return 1;
return power(x,mod-2)%mod;
}
void calc(){//数论分块
int r;ans2=1;
for(int l=1;l<=n;l=r+1){
r=n/(n/l);
ans2=1ll*ans2*power(1ll*fac[r]*inv(fac[l-1])%mod,(2ll*num[n/l]-1)%mod2)%mod;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
sieve();
cin>>t;
while(t--){
cin>>n;
ans1=power(fac[n],2*n);
calc();
ans2=1ll*ans2*ans2%mod;
ans=1ll*ans1*inv(ans2)%mod;
cout<<ans<<"\n";
}
return 0;
}