求：
\[\prod_{i=1}^n\prod_{j=1}^n\frac{lcm(i,j)}{gcd(i,j)}\ (\bmod\ 104857601)\\1 \leq n \leq 1000000 \]而且这个题的时限卡在 200ms，空间卡在 7.81MB。
先推式子。
我们分开考虑，最后用上面的答案乘下面的答案在 \(\bmod\ 104857601\) 下的逆元即可。
分别记上下的答案为 \(Ans1\)，\(Ans2\)。
上半部分到此为止，开始考虑下半部分。
\[Ans2 =\prod_{i=1}^n\prod_{j=1}^ngcd^2(i,j)\\ =\left(\prod_{i=1}^n\prod_{j=1}^ngcd(i,j)\right)^2\\ =\left(\prod_{i=1}^ni\times\prod_{i=2}^n\prod_{j=1}^{i-1}gcd(i,j)\times\prod_{i=1}^{n-1}\prod_{j=i+1}^ngcd(i,j)\right)^2\\ =\left(\prod_{i=1}^ni\times\left(\prod_{i=2}^n\prod_{j=1}^{i-1}gcd(i,j)\right)^2\right)^2\\ =\left(n!\times\left(\prod_{i=2}^n\prod_{j=1}^{i-1}gcd(i,j)\right)^2\right)^2\\ \]下面来考虑如何化简下式。
\[\prod_{i=2}^n\prod_{j=1}^{i-1}gcd(i,j) \]分两种情况。
如果 \(i\) 和 \(j\) 互质，显然 \(gcd(i,j)=1\)；如果 \(i\) 和 \(j\) 不互质，我们设 \(gcd(i,j)=g\)，则 \(i=p*g\)，\(j=q*g\) 且 \(gcd(p,q)=1\)。又因为 \(i>j\)，所以 \(p>q\)。
因此我们由枚举所有的数对，换成枚举“互质”的数对。
具体地，\(i\) 仍然从 \(2\) 枚举到 \(n\)，然后从 \([1,i-1]\) 中找到与 \(i\) 互质的 \(j\)，那么我们就可以考虑这一对互质数在原式中的贡献。
所谓“贡献”，就是指所有 \(p=i,q=j\) 的数对在原式的贡献，这里的 \(p\) 和 \(q\) 是上文设出的，代表这对数是它们 \(gcd\) 的“几倍”。容易发现，只要枚举到所有的“互质数对”，由此考虑的贡献就是不重不漏的。
显然，\(1*i,1*j\)，\(2*i,2*j\)，\(3*i,3*j\) 等都是符合上文要求的，对原式有贡献的数对。
那么这样的数对有多少呢？如果最大的数对是 \(x*i,x*j\)，则 \(x*i\leq n\)，即 \(x\leq\lfloor\dfrac{n}{i}\rfloor\)
因此我们可以计算“互质数对” \(i\)，\(j\) 的贡献如下：
\[\prod_{g=1}^{\lfloor\frac{n}{i}\rfloor}gcd(g*i,g*j)=\prod_{g=1}^{\lfloor\frac{n}{i}\rfloor}g*gcd(i,j)=\prod_{g=1}^{n/i}g=\lfloor\dfrac{n}{i}\rfloor! \]发现我们仍没有降低复杂度：先枚举 \(i\)，再遍历所有小于 \(i\) 的，与 \(i\) 互质的数 \(j\)，\(O(n^2)\)。
但我们惊喜地发现刚才计算贡献的式子与 \(j\) 无关。而且“所有小于 \(i\) 的，与 \(i\) 互质的数”的数量是固定的，即欧拉函数 \(\phi(i)\)。
再代回原式。
\[\prod_{i=2}^n\prod_{j=1}^{i-1}gcd(i,j) =\prod_{i=2}^n\prod_{j=1,i\perp j}^{i-1}\lfloor\dfrac{n}{i}\rfloor! =\prod_{i=2}^n\left(\lfloor\dfrac{n}{i}\rfloor!\right)^{\phi(i)} \]继续回代。
\[Ans2 =\left(n!\times\left(\prod_{i=2}^n\prod_{j=1}^{i-1}gcd(i,j)\right)^2\right)^2\\ =\left(n!\times\left(\prod_{i=2}^n\left(\lfloor\dfrac{n}{i}\rfloor!\right)^{\phi(i)}\right)^2\right)^2\\ =\left(n!\times\prod_{i=2}^n\left(\lfloor\dfrac{n}{i}\rfloor!\right)^{2\phi(i)}\right)^2\\ =(n!)^2\times\prod_{i=2}^n\left(\lfloor\dfrac{n}{i}\rfloor!\right)^{2\phi(i)*2}\\ =(n!)^2\times\prod_{i=2}^n\left(\lfloor\dfrac{n}{i}\rfloor!\right)^{4\phi(i)}\\ \]于是整个题目的答案为：
\[Ans =\dfrac{Ans1}{Ans2} =\dfrac{(n!)^{2n}}{(n!)^2\times\prod_{i=2}^n\left(\lfloor\dfrac{n}{i}\rfloor!\right)^{4\phi(i)}} \]于是我们就可以 \(O(n)\) 地快乐计算了，最后用费马小定理求 \(Ans2\) 的逆元即可。
吗？
然后你就会收获一枚亮闪闪的 MLE。
如果根据这个式子计算，我们需要开两个数组，一个是求 \(\lfloor\dfrac{n}{i}\rfloor!\) 的阶乘数组，一个是 \(4\phi(i)\) 要用的 \(\phi\) 数组，还有欧拉筛求 \(\phi\) 所需的 \(vis\) 数组和存质数的 \(vector\)。
然而只有 7.81MB 的空间。就算我们全开 int，\(vis\) 数组用 \(bool\)，\(vector\) 占用空间按照 \(\sqrt{n}\) 计算：
所以我们必须要优化空间。考虑优化这个部分，会发现有很多数被重复计算了。我们先尝试展开这个式子。
\[\prod_{i=2}^n\left(\lfloor\dfrac{n}{i}\rfloor!\right)^{4\phi(i)} =\prod_{i=2}^n\left(1\times2\times...\times\lfloor\dfrac{n}{i}\rfloor\right)^{4\phi(2)}\\ =1^{4\phi(2)}\times2^{4\phi(2)}\times...\times\lfloor\dfrac{n}{2}\rfloor^{4\phi(2)}\\ \times1^{4\phi(3)}\times2^{4\phi(3)}\times...\times\lfloor\dfrac{n}{3}\rfloor^{4\phi(3)}\\ \times1^{4\phi(4)}\times2^{4\phi(4)}\times...\times\lfloor\dfrac{n}{4}\rfloor^{4\phi(4)}\\ ......\\ \times1^{4\phi(\lfloor\frac{n}{2}\rfloor)}\times\lfloor\dfrac{n}{\lfloor\frac{n}{2}\rfloor}\rfloor^{4\phi(\lfloor\frac{n}{2}\rfloor)}\\ ......\\ \times1^{4\phi(n)}\\ \]我们改变枚举顺序，原来是一行一行地枚举，现在我们一列一列地枚举。容易发现最多 \(\lfloor\dfrac{n}{2}\rfloor\) 列。
于是原式变成：
其中 \(k_i\) 表示 \(i\) 在原式中的总次数。那么我们怎么快速求出这个 \(k_i\) 呢？
考虑再把原式换一种方式展开。
\[\prod_{i=2}^n\left(\lfloor\dfrac{n}{i}\rfloor!\right)^{4\phi(i)} =\left(\lfloor\dfrac{n}{2}\rfloor!\right)^{4\phi(2)} \times\left(\lfloor\dfrac{n}{3}\rfloor!\right)^{4\phi(3)} \times\left(\lfloor\dfrac{n}{4}\rfloor!\right)^{4\phi(4)} ... \times\left(\lfloor\dfrac{n}{n}\rfloor!\right)^{4\phi(n)} \]显然一个数 \(x\) 在各个项里要么不出现，要么出现一次。只有当 \(\lfloor\dfrac{n}{i}\rfloor>x\) 的时候，其内才出现 \(x\)。
又因为各个项内的 \(\lfloor\dfrac{n}{i}\rfloor\) 是随 \(i\) 增大而减小的，换句话说，不增，所以一旦给定一个数 \(x\)，我们就可以找到一个数 \(d=\lfloor\dfrac{n}{x}\rfloor\) 使得 \(\lfloor\dfrac{n}{2}\rfloor\) ~ \(\lfloor\dfrac{n}{d}\rfloor\) 均大于等于 \(x\)，并且 \(\lfloor\dfrac{n}{d+1}\rfloor\) ~ \(\lfloor\dfrac{n}{n}\rfloor\) 均小于 \(x\)。
于是 \(x\) 出现的总次数就是 \(\lfloor\dfrac{n}{2}\rfloor!\) ~ \(\lfloor\dfrac{n}{d}\rfloor!\) 这些项的次数之和，即 \(4\phi(2)+4\phi(3)+...+4\phi(d)\)。我们设一个前缀和函数 \(S(n)=\sum_{i=2}^{d}\phi(i)\)，则 \(x\) 的总次数 \(k_x\) 是 \(=4*S(d)=4*S(\dfrac{n}{x})\)。
下面给出为什么 \(d\) 等于 \(\lfloor\dfrac{n}{x}\rfloor\) 的证明。
把我们的序列提取出来，前文已经叙述，显然这是个不升的序列，如果学过数论分块下面会很好理解。
\[\lfloor\dfrac{n}{2}\rfloor,\lfloor\dfrac{n}{3}\rfloor,\lfloor\dfrac{n}{4}\rfloor,...,\lfloor\dfrac{n}{d}\rfloor,...,\lfloor\dfrac{n}{n-1}\rfloor,\lfloor\dfrac{n}{n}\rfloor \]我们取 \(d=\lfloor\dfrac{n}{x}\rfloor\)，则有 \(n=dx+r,r<x\)，其实相当于带余除法。显然 \(\lfloor\dfrac{n}{d}\rfloor\geq x\)。
\[\lfloor\dfrac{n}{d+1}\rfloor\\ =\lfloor\dfrac{dx+r}{d+1}\rfloor\\ =\lfloor\dfrac{dx+x+r-x}{d+1}\rfloor\\ =\lfloor\dfrac{(d+1)x+(r-x)}{d+1}\rfloor =\lfloor\dfrac{(d+1)x+(r-x)}{d+1}\rfloor =\lfloor x+\dfrac{(r-x)}{d+1}\rfloor \]
可以这么理解,如果取 \(d\) 的时候不取整，会导致 \(d\) 偏大，这样 \(\lfloor\dfrac{n}{d}\rfloor\) 才刚好等于 \(x\)。但取整后的 \(d\) 是小于等于不取整的 \(d\) 的，因而 \(\lfloor\dfrac{n}{d}\rfloor\) 的分母偏小，整体就会偏大。整除也不影响偏大的结果。
再证明 \(\lfloor\dfrac{n}{d+1}\rfloor<x\)。因为刚才有 \(r<x\)，所以 \(r-x<0\)，又因为 \(d+1>0\)，所以 \(\dfrac{(r-x)}{d+1}<0\)。
\[d=\lfloor\dfrac{n}{x}\rfloor,\lfloor\dfrac{n}{d}\rfloor\geq x,\lfloor\dfrac{n}{d+1}\rfloor<x。 \]
\(x\) 是个整数，加上一个小于 \(0\) 的数后取整，必然是严格小于 \(x\) 的。所以：
至此我们已经能够求出每个数的次数 \(k_i\)。再回顾刚才的式子：
\[\prod_{i=2}^n\left(\lfloor\dfrac{n}{i}\rfloor!\right)^{4\phi(i)} =\prod_{i=1}^{\lfloor\frac{n}{2}\rfloor}i^{k_i} =\prod_{i=1}^{\lfloor\frac{n}{2}\rfloor}i^{4*S(\frac{n}{i})} \]再回代：
\[Ans2 =(n!)^2\times\prod_{i=2}^n\left(\lfloor\dfrac{n}{i}\rfloor!\right)^{4\phi(i)} =\prod_{i=1}^{\lfloor\frac{n}{2}\rfloor}i^{4*S(\frac{n}{i})} \]于是整个题目的答案为：
\[Ans =\dfrac{Ans1}{Ans2} =\dfrac{(n!)^{2n}}{(n!)^2\times\prod_{i=1}^{\lfloor\frac{n}{2}\rfloor}i^{4*S(\frac{n}{i})}} \]虽然时间复杂度上只有 \(\dfrac{1}{2}\) 的常数优化，但我们发现阶乘数组已经不再需要了。\(n!\) 虽然是阶乘但不需要数组，一个变量就可存下。至于前缀和 \(S(n)\) 完全可以直接在 \(\phi(n)\) 数组上直接原地前缀和，所需空间小于 7.81MB。
至此此题做完，但有一些细节需要。注意到 \(S(n)\) 是在指数上的，而我们取前缀和的时候必定会进行取模。实际上 \(a^x\) 与 \(a^{x \bmod p}\) 在 \(\bmod p\) 意义下并不相等。有一个欧拉函数的推论如下：
\[a^x\equiv a^{x\bmod \phi(x)}(\bmod p) \]又因为 \(p\) 为质数，\(\phi(p)\) 就等于 \(p-1\)。所以：
\[a^x\equiv a^{x\bmod p-1}(\bmod p) \]所以在求前缀和时由模 \(p\) 改为模 \(p-1\) 即可。
代码：
// Problem: P5221 Product
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5221
// Memory Limit: 7 MB
// Time Limit: 200 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define INF 0x7fffffff
#define MAXN 1000005
#define eps 1e-9
#define foru(a,b,c) for(int a=b;a<=c;a++)
#define RT return 0;
#define db(x) cout<<endl<<x<<endl;
#define LL long long
#define LXF int
#define RIN rin()
#define HH printf("\n")
using namespace std;
inline LXF rin(){
LXF x=0,w=1;
char ch=0;
while(ch<'0'||ch>'9'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
return x*w;
}
const LL p=104857601;
int phi[MAXN];
bitset<MAXN> vis;
vector<int> prim;
int n;
LL jc=1;
LL ksm(LL a,LL b){
LL ret=1;
a%=p;
while(b){
if(b&1) ret=(ret*a)%p;
b>>=1,a=(a*a)%p;
}
return ret;
}
void pre(){
for(int i=2;i<=MAXN-5;i++){
if(i<=n){
jc=(LL)jc*(LL)i%p;
}
if(!vis[i]){
prim.emplace_back(i);
phi[i]=i-1;
}
for(int j=0;j<prim.size()&&i*prim[j]<=MAXN-5;j++){
vis[i*prim[j]]=1;
if(i%prim[j]==0){
phi[i*prim[j]]=phi[i]*prim[j];
break;
}
phi[i*prim[j]]=phi[i]*(prim[j]-1);
}
phi[i]=(LL)((LL)phi[i-1]+(LL)phi[i])%(p-1);//模phi(p)=p-1
}
}
signed main(){
n=RIN;
pre();
LL ans1=ksm((LL)jc,(LL)2*n),ans2=jc*jc%p;
int top=n>>1;
for(int i=1;i<=top;i++){
ans2*=ksm(i,4ll*(LL)phi[n/i]);//phi是在指数上
ans2%=p;
}
ans1=ans1*ksm(ans2,p-2)%p;//求Ans2逆元
cout<<ans1;
return 0;
}