LuoguP5221 Product

题目地址

题目链接

题解

注，下方((i,j))均指(gcd(i,j))，以及证明过程有一定的跳步，请确保自己会莫比乌斯反演的基本套路。

介绍本题的(O(n))和(O(nsqrt{n}))做法，本题还有(O(nlogn))做法，需要用到欧拉函数，或者是从质因子角度考虑也可以得到另外一个(O(n))做法。

题目就是求

[prod_{i=1}^nprod_{j=1}^nfrac{ij}{(i,j)^2} ]

考虑分解一下

[prod_{i=1}^nprod_{j=1}^nfrac{ij}{(i,j)^2}=frac{prod_{i=1}^nprod_{j=1}^nij}{prod_{i=1}^nprod_{j=1}^n(i,j)^2} ]

对于分子可得

[egin{aligned} &prod_{i=1}^nprod_{j=1}^nij\ &=prod_{i=1}^niprod_{j=1}^nj\ &=prod_{i=1}^ni*n!\ &=(n!)^{2n} end{aligned} ]

对于分母，我们考虑莫比乌斯反演

[egin{aligned} &prod_{i=1}^nprod_{j=1}^n(i,j)^2\ &=prod_{d=1}^nd^{2sum_{i=1}^nsum_{j=1}^n[(i,j)=d]}\ &=prod_{d=1}^nd^{2sum_{i=1}^{lfloorfrac{n}{d} floor}sum_{j=1}^{lfloorfrac{n}{d} floor}[(i,j)=1]}\ &=prod_{d=1}^nd^{2sum_{k=1}^{lfloorfrac{n}{d} floor}mu(k)lfloorfrac{n}{kd} floor^2}\ end{aligned} ]

至此，枚举(d)，对指数整除分块，即可(O(nsqrt{n}))解决此题。

容易发现(lfloorfrac{n}{d} floor)是可以整除分块的。那么怎么处理区间([l,r])的(d)呢，将它展开，其实就是(frac{r!}{(l-1)!})，由于出题人卡空间，所以可以直接计算阶乘而不是预处理（复杂度同样是(O(n))，每个数只会被遍历一次）

那么就可以做到(O(n))解决本题了。

#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;

const int mod = 104857601;
const int p = 104857600;
const int N = 1000010;

bool vis[N];
short mu[N];
int pr[N], cnt = 0;
int fac;

int power(int a, int b, int Mod) {
	int ans = 1;
	while(b) {
		if(b & 1) ans = (ll)ans * a % Mod;
		a = (ll)a * a % Mod;
		b >>= 1;
	}
	return ans % Mod;
}

void init(int n) {
	mu[1] = 1;
	for(int i = 2; i <= n; ++i) {
		if(!vis[i]) pr[++cnt] = i, mu[i] = -1;
		for(int j = 1; j <= cnt && i * pr[j] <= n; ++j) {
			vis[i * pr[j]] = 1;
			if(i % pr[j] == 0) break;
			mu[i * pr[j]] = -mu[i];
		}
		mu[i] += mu[i - 1];
	}
	fac = 1;
	for(int i = 1; i <= n; ++i) fac = (ll)fac * i % mod;
}

int n;

int calc2(int n) {
	int ans = 0;
	for(int l = 1, r; l <= n; l = r + 1) {
		r = n / (n / l);
		ans = (ans + (ll)(n / l) * (n / l) % p * (mu[r] - mu[l - 1] + p) % p) % p;
	}
	return ans % p;
}

int main() {
	scanf("%d", &n);
	init(n);
	int ans = 1;
	int sum = power((ll)fac * fac % mod, n, mod);
	for(int l = 1, r; l <= n; l = r + 1) {
		r = n / (n / l); fac = 1ll;
		for(int i = l; i <= r; ++i) fac = (ll)fac * i % mod;
		int t = power((ll)fac * fac % mod, calc2(n / l), mod);
		ans = (ll)ans * t % mod;
	}
	printf("%lld
", (ll)sum * power(ans, mod - 2, mod) % mod);
}