这题其实没必要反演……
有 \(\sum\limits_{i = 1}^n \sum\limits_{j = 1}^n [\gcd(i,j) = 1] = 2\sum\limits_{i = 1}^n \varphi(i) - 1\)，然后这题就没了……
好的，如果您看到了这里，请忽略以上内容。
首先题目要求 \(\prod\limits_{i = 1}^n\prod\limits_{j = 1}^n \dfrac{\text{lcm}(i,j)}{\gcd(i,j)}\)，根据小学奥数，把 \(\text{lcm}\) 拆开，得到 \(\prod\limits_{i = 1}^n\prod\limits_{j = 1}^n \dfrac{ij}{\gcd^2(i,j)}\)。
由于是乘法，可以把分子和分母拆开，那么分子部分即 \(\prod\limits_{i = 1}^n\prod\limits_{j = 1}^n ij = (n!)^{2n}\)。
然后看分母。
这十分套路啊…… \[\begin{align*}
& \prod\limits_{i = 1}^n \prod\limits_{j = 1}^n \text{gcd}^2(i,j) \\
= & (\prod\limits_{i = 1}^n \prod\limits_{j = 1}^n \gcd(i,j))^2 \\
= & (\prod\limits_{d = 1}^n d^{\sum\limits_{i = 1}^n \sum\limits_{j = 1}^n [\gcd(i,j) = d]})^2
\end{align*}\]
指数更熟悉了不是吗？
这个要是不会推就别说你会莫反。
得到 \[\begin{align*}
& (\prod\limits_{d = 1}^n d^{\sum\limits_{i = 1}^n \sum\limits_{j = 1}^n [\gcd(i,j) = d]})^2 \\
= & (\prod\limits_{d = 1}^n d^{\sum\limits_{i = 1}^{\lfloor \frac n d \rfloor} \mu(i) (\lfloor \frac n {id} \rfloor)^2})^2
\end{align*}\]
那么我们需要预处理 \(\sum\limits_{i = 1}^n \mu(i) (\lfloor \frac n i \rfloor)^2\)。
本来想 \(O(n \sqrt n)\) 预处理，但是考虑到 \(n \le 10^6\)，需要做到 \(O(n \log n)\)。
想到了什么？
观察到对于 \(n \in [ki,(k + 1)i)\)，有 \(\lfloor \dfrac n i \rfloor = k\)。
于是枚举倍数就可以了。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
using namespace std;
const int N = 1e6;
const int mod = 19260817;
int T,n;
int vis[N + 5],prime[N + 5],cnt,mu[N + 5];
int fac[N + 5],f[N + 5];
int ans;
inline int fpow(int a,int b)
{
int ret = 1;
for(;b;b >>= 1)
(b & 1) && (ret = (long long)ret * a % mod),a = (long long)a * a % mod;
return ret;
}
int main()
{
mu[1] = 1;
for(register int i = 2;i <= N;++i)
{
if(!vis[i])
mu[prime[++cnt] = i] = -1;
for(register int j = 1;j <= cnt && i * prime[j] <= N;++j)
{
vis[i * prime[j]] = 1;
if(!(i % prime[j]))
break;
else
mu[i * prime[j]] = -mu[i];
}
}
fac[0] = 1;
for(register int i = 1;i <= N;++i)
{
fac[i] = (long long)fac[i - 1] * i % mod;
for(register int j = 1;i * j <= N;++j)
f[i * j] = (f[i * j] + (long long)mu[i] * j * j % (mod - 1)) % (mod - 1),f[min(i * (j + 1),N + 1)] = (f[min(i * (j + 1),N + 1)] - (long long)mu[i] * j * j % (mod - 1)) % (mod - 1);
}
for(register int i = 1;i <= N;++i)
f[i] = (f[i - 1] + f[i] + mod - 1) % (mod - 1);
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
ans = 1;
for(register int l = 1,r;l <= n;l = r + 1)
{
r = n / (n / l);
ans = (long long)ans * fpow((long long)fac[r] * fpow(fac[l - 1],mod - 2) % mod,f[n / l]) % mod;
}
printf("%d\n",(int)(((long long)fpow(fac[n],2 * n) * fpow(ans,mod - 3) % mod + mod) % mod));
}
}