\begin{aligned} Ans &= \prod_a^n\prod_b^n \cfrac {lcm(a, b)^2} {ab}\\ &= \prod_a^n\prod_b^n \cfrac {ab} {\gcd(a, b)^2}\\ &= \cfrac {\prod_a^n\prod_b^n ab} {\prod_a^n\prod_b^n gcd(a, b)^2}\\ &= \cfrac {(n!)^{2n}} {\prod_a^n\prod_b^n gcd(a, b)^2} \end{aligned}
\begin{aligned} &\prod_a^n\prod_b^n gcd(a, b)^2\\ =&(\prod_d^n d^{\sum_a^n\sum_b^n [\gcd(a, b) = d]})^2\\ =&(\prod_d^n d^{\sum_a^{\frac n d}\sum_b^{\frac n d} [\gcd(a, b) = 1]})^2\\ =&(\prod_d^n d^{\sum_a^{\frac n d}\sum_b^{\frac n d} [\gcd(a, b) = 1]})^2\\ =&(\prod_d^n d^{(2\sum_i^{\frac n d}\varphi(i)) - 1})^2\\ =&(\prod_d^n d^{f(d)})^2&&f(d) = (2\sum_i^{\lfloor\frac n d\rfloor}\varphi(i)) - 1\\ =&\prod_d^n d^{2f(d)}\\ \end{aligned}
d可以数论分块
我是个傻子,忘了a^n\pmod p = a^{n\bmod\varphi(p)}\pmod p(a, p互质),因为p是个伟大的有意义的质数所以说\varphi(p) = p-1
#include <bits/stdc++.h>
const int mod = 19260817, N = 1000000 + 10;
long long phi[N], primes[N], phisum[N];
bool not_prime[N];
inline void pre_phi(int n)
{
phi[1] = 1;
for (int i = 2; i <= n; ++i)
{
if (!not_prime[i])
{
phi[i] = i - 1;
primes[++primes[0]] = i;
}
for (int j = 1; j <= primes[0]; ++j)
{
if (i * primes[j] > n)
break;
not_prime[i * primes[j]] = true;
if (i % primes[j] == 0)
{
phi[i * primes[j]] = phi[i] * primes[j];
break;
}
else
phi[i * primes[j]] = phi[i] * (primes[j] - 1); // phi[primes[j]]
}
}
for (int i = 1; i <= n; ++i)
phisum[i] = (phi[i] + phisum[i - 1]) % (mod - 1); // 指数取模
}
long long fact[N];
inline void pre_fact(int n)
{
fact[0] = 1;
for (int i = 1; i <= n; ++i)
fact[i] = fact[i - 1] * i % mod;
}
long long power(long long a, int n)
{
long long ret = 1;
while (n)
{
if ( n & 1)
ret = ret * a % mod;
a = a * a % mod;
n >>= 1;
}
return ret;
}
int inv(int val) { return power(val, mod - 2); }
inline int f(int n, int d)
{
return (phisum[n / d] * 4 - 2 + mod - 1) % (mod - 1); // 指数取模
}
int main(void)
{
pre_phi(N - 1);
pre_fact(N - 1);
int T;
std::cin >> T;
while (T--)
{
int n;
std::cin >> n;
long long ans2 = 1;
for (int l = 1, r; l <= n; l = r + 1)
{
r = n / (n / l);
ans2 = ans2 * power(fact[r] * inv(fact[l-1]) % mod, f(n, l)) % mod;
}
long long ans1 = power(fact[n], n * 2);
std::cout << ans1 * inv(ans2) % mod << std::endl;
}
}