mydcwfy's Blog

LOJ6179 Pyh 的求和

Posted on
Symbols count in article: 2.7k Reading time ≈ 6 mins.

题意：求 $\sum_{i = 1} ^ n \sum_{j = 1} ^ m \varphi(ij)\bmod 998244353$。$T(T\leq 10 ^ 5)$ 组数据，$n, m\leq 10 ^ 5$，4s，64MB。

首先一个容易发现的性质是 $\varphi(ij) = \dfrac{\varphi(i) \varphi(j) \gcd(i, j)}{\varphi(\gcd(i, j))}$。考虑每个质因数的贡献即可。

那么一阵推导（默认 $n\leq m$）：

容易发现后面的 $\sum_{d | T} \dfrac {d\mu(\dfrac Td)}{\varphi(d)}$ 可以在 $O(n\log n)$ 的时间预处理，如果求出了前面的一坨，容易单次 $O(\sqrt n)$ 整除分块计算。问题在于前面的这两个不是很好和整除分块一起计算。

考虑有两种处理办法：

  1. 预处理 $f(n, m, T) = \sum_{i = 1} ^ n \sum_{j = 1} ^ m \varphi(iT) \varphi(jT)$ 并使用前缀和，这样就可以使用整除分块。
  2. 预处理 $g(n, T) = \sum_{i = 1} ^ n f(iT)$，不使用前缀和和整除分块。

两个可以平衡规划一下，考虑到神秘的空间限制，大概确定一个阈值即可， $\dfrac mT$ 小于他的使用预处理整除分块，否则使用暴力。时间限制比较宽松，只要平衡规划一般能通过。

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
55
56
57
58
59
60
61
62
63
64
65
66
const int N = 1e5 + 10, B = 50, Mod = 998244353;

void sieve(int n)
{
	phi[1] = mu[1] = 1;
	for (int i = 2; i <= n; ++ i)
	{
		if (!st[i]) prime[++ cnt] = i, phi[i] = i - 1, mu[i] = -1;
		for (int j = 1; j <= cnt && i * prime[j] <= n; ++ j)
		{
			st[i * prime[j]] = true;
			if (i % prime[j] == 0) {
				phi[i * prime[j]] = phi[i] * prime[j];
				break;
			}
			phi[i * prime[j]] = phi[i] * (prime[j] - 1);
			mu[i * prime[j]] = -mu[i];
		}
	}
	for (int i = 1; i <= n; ++ i) adj(mu[i]), invphi[i] = qpow(phi[i]);
	for (int i = 1; i <= n; ++ i)
		for (int d = 1; d * i <= n; ++ d)
			g[i * d] = (g[i * d] + (LL) d * invphi[d] % Mod * mu[i]) % Mod;
	int cnt = 0;
	for (int T = 1; T <= n; ++ T)
	{
		f[T].push_back(0);
		for (int i = 1, tmp; i * T <= n; ++ i)
			f[T].push_back(adj(tmp = f[T].back() + phi[i * T] - Mod));
		cnt += f[T].size();
	}
	for (int s1 = 1; s1 <= B; ++ s1)
		for (int s2 = 1; s2 <= B; ++ s2)
		{
			auto &v = S[s1][s2];
			v.push_back(0);
			for (int i = 1, ed = std::min(n / s1, n / s2); i <= ed; ++ i)
				v.push_back((v.back() + (LL) f[i][s1] * f[i][s2] % Mod * g[i]) % Mod);
			cnt += v.size();
		}
	std::cerr << (cnt * 4 + std::abs(&mem1 - &mem2)) / 1048576. << " MB\n";
}

void work()
{
	int n, m, res = 0;
	scanf("%d %d", &n, &m);
	if (n > m) std::swap(n, m);
	for (int i = 1; i <= m / B; ++ i)
		res = (res + (LL) g[i] * f[i][n / i] % Mod * f[i][m / i]) % Mod;
	for (int l = m / B + 1, r, tn, tm; l <= n; l = r + 1)
	{
		r = std::min(n / (tn = n / l), m / (tm = m / l));
		adj(adj(res += S[tn][tm][r] - Mod) -= S[tn][tm][l - 1]);
	}
	printf("%d\n", res);
}

int main()
{
	sieve(1e5 + 1);
	int T;
	std::cin >> T;
	while (T --) work();
	return 0;
}