CWOI S C0327 C 数

题意

原 FJWC2020 Day5 T2 lg。

给定 n 和 m。计算

$$\prod_{1 \le x_{i} \le m} \mathrm{lcm}(x)^{\gcd(x)} \pmod {998,244,353}$$

其中 x 是一个长度为 n，每个值都在 1 到 m 之间的整数序列。

解析

首先有一个关于 gcd 的结论，$\gcd(a,b) = \sum_{d|a \text{and} d|b} \varphi(d)$，这是从 $\sum_{d|n} \varphi{d} = n$ 得出的。所以我们可以把式子变形成：

$$\prod_{1 \le x_{i} \le m} \mathrm{lcm}(x)^{\sum_{d|x_{i}} \varphi(d)}$$

将 Σ 从指数拿下来，得到：

$$\prod_{1 \le x_{i} \le m} \prod_{d|x_{i}} \mathrm{lcm}(x)^{\varphi(d)}$$

交换两个 Π 的位置，得到：

$$\prod_{1 \le d \le m} \prod_{d|x_{i}} \mathrm{lcm}(x)^{\varphi(d)}$$

由于第二个 Π 中，满足条件的 x 都是 d 的倍数，可以把 x 全部除以 d，得到：

$$\prod_{1 \le d \le m} \prod_{1 \le x_{i} \le \left\lfloor\frac{m}{d}\right\rfloor} [d\mathrm{lcm}(x)]^{\varphi(d)}$$

然后拆成两部分：

$$\prod_{1 \le d \le m} \left[\prod_{1 \le x_{i} \le \left\lfloor\frac{m}{d}\right\rfloor} \mathrm{lcm}(x)\right]^{\varphi(d)} d^{\varphi(d)\left\lfloor\frac{m}{d}\right\rfloor^{n}}$$

后面的那一部分很好处理，模数是 998244353，直接欧拉定理降幂，然后快速幂。

前面那部分，考虑枚举每一个素数对于 lcm 的贡献。如果 lcm 中素数 p 的指数为 c，则 x 中一定存在一个数有因子 $p^c$，且任何一个数都不含因子 $p^{c+1}$。计算这个可以用不包含 $p^{c+1}$ 的减去不包含 $p^c$ 的。

实现

using mint = static_modint<998'244'353>;

auto pow_mod(long long x, long long y, long long mod)
{
	long long res = 1;
	while (y) {
		if (y & 1) res = res * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}

std::pair<std::vector<int>, std::vector<int>> linear_sieve(int n)
{
	std::vector<bool> is_prime(n + 1, true);
	std::vector<int> prime, phi(n + 1);

	phi[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (is_prime[i]) {
			prime.emplace_back(i);
			phi[i] = i - 1;
		}
		for (auto j : prime) {
			if (i * j > n) break;
			is_prime[i * j] = false;
			if (i % j != 0) {
				phi[i * j] = phi[i] * phi[j];
			} else {
				phi[i * j] = phi[i] * j;
				break;
			}
		}
	}

	return {prime, phi};
}

int main()
{
	int n, m;
	std::cin >> n >> m;

	auto [prime, phi] = linear_sieve(m);

	auto calc = [&prime, n](int m)
	{
		mint res = 1;
		for (auto p : prime) {
			if (p > m) break;
			int k = 1;
			long long v = p;
			int cnt = 0;
			while (v <= m) {
				cnt = (cnt + k * ((pow_mod(m - m / (v * p), n, mint::phi()) - pow_mod(m - m / v, n, mint::phi())) % mint::phi())) % mint::phi();
				k++;
				v *= p;
			}
			if (cnt < 0) cnt += mint::phi();
			res *= mint{p}.pow(cnt);
		}
		return res;
	};

	mint ans = 1;
	mint last_calc;
	int last_d = -1;

	for (int d = 1; d <= m; d++) {
		if (last_d != m / d) {
			last_d = m / d;
			last_calc = calc(m / d);
		}
		ans *= last_calc.pow(phi[d]) * mint{d}.pow(phi[d] * pow_mod(m / d, n, mint::phi()));
	}

	std::cout << ans.val() << std::endl;
}