写得我头疼。
容易发现,任意两个数要拼成一个正方形,最小边长是 (operatorname{lcm}(i,j))
那么需要用的数量就是 (dfrac{operatorname{lcm}(i,j)^2}{i cdot j})
所以我们要求的就是 (displaystyle prod_{i=1}^N prod_{j=1}^N dfrac{operatorname{lcm}(i, j)^2}{i cdot j})
转化一下就是 (displaystyle prod_{i=1}^N prod_{j=1}^N dfrac{i cdot j}{gcd(i,j)^2})
接下来就是 (displaystyle dfrac{large (n!)^{2n}}{displaystyle prod_{i=1}^N prod_{j=1}^N gcd(i, j)^2})
然后我们令 (d = gcd(i, j))
那么 (displaystyle dfrac{large (n!)^{2n}}{displaystyle prod_{d=1}^N d^{2 cdot 2 sum_{i=1}^{lfloor frac{N}{d} floor } sum_{j=1}^{lfloor frac{N}{d} floor }[gcd(i,j)=1]}})
然后经过莫比乌斯反演(懒得写了)
然后得到 (displaystyle dfrac{large (n!)^{2n}}{displaystyle prod_{d=1}^N d^{2 cdot 2 sum_{k=1}^{lfloor frac{N}{d} floor} mu(k) cdot (lfloor frac{N}{kd} floor )^2}})
感觉是可以做了,但是我写挂了,然后换了个方法。。。
你考虑这就是求了一个数表内互质的数
那么可以换成
注:(-1) 是因为 (varphi(1)) 被算了两遍。
下面就是各位的代码能力了。。。
下面是我的代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
const ll MAXN = 1e6+10, MOD = 19260817;
ll N, T, fac[MAXN], phi[MAXN], prime[MAXN], cnt, vis[MAXN], inv[MAXN];
ll ks(ll, ll);
ll f(ll);
int main() {
scanf("%lld", &T);
fac[0] = fac[1] = inv[0] = inv[1] = 1;
for (ll i = 2; i <= MAXN - 10; i++)
fac[i] = fac[i-1] * i % MOD, inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
for (ll i = 2; i <= MAXN - 10; i++)
inv[i] = inv[i-1] * inv[i] % MOD;
phi[1] = 1;
for (ll i = 2; i <= MAXN - 10; i++) {
if (!vis[i]) prime[++cnt] = i, phi[i] = i-1;
for (ll j = 1; j <= cnt && prime[j] * i <= MAXN - 10; j++) {
vis[i * prime[j]] = 1;
if (i % prime[j]) {
phi[i * prime[j]] = phi[i] * phi[prime[j]];
} else {
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
}
}
for (ll i = 1; i <= MAXN - 10; i++)
phi[i] = (phi[i] + phi[i-1]) % (MOD - 1); // phi出现在指数,那么 mod (MOD-1)
while (T--) {
scanf("%lld", &N);
ll up = ks(fac[N], (2 * N) % MOD) % MOD;
ll down = 1;
for (ll l = 1, r = 0; l <= N; l = r + 1) {
r = (N / (N / l));
ll gx = phi[N / l] * 2 - 1;
down = down * ks(fac[r] * inv[l-1] % MOD, gx) % MOD;
}
down = down * down % MOD;
printf("%lld
", up * ks(down, MOD-2) % MOD);
}
return 0;
}
ll ks(ll n, ll tim) {
ll ret = 1;
while (tim) {
if (tim & 1) ret = ret * n % MOD;
n = n * n % MOD;
tim >>= 1;
}
return ret % MOD;
}