name 题解

题面描述

给定一个长度为 n 的数列 a1, a2, a3, …, an。

令 $\displaystyle k=(\sum_{i=1}^{n}\sum_{j=i+1}^{n}\mathrm{lcm}(a_i,a_j)) \bmod 3999971$，求一个 k + 1 的正整数倍 S，使得 S 的数位累加和最小。

解题思路

首先我们先考虑如何求出 k。

注意到 $\displaystyle \sum_{i=1}^{n}\sum_{j=i+1}^{n}\mathrm{lcm}(a_i,a_j)$ 第二个 ∑ 不是从 1 开始的这让我们很难受，所以：

$$ \sum_{i=1}^{n}\sum_{j=i+1}^{n}\mathrm{lcm}(a_i,a_j)=\frac{\sum_{i=1}^{n}\sum_{j=1}^{n}\mathrm{lcm}(a_i,a_j)-\sum_{i=1}^{n}{a_i}}{2} $$

现在我们的就是要算 $\displaystyle \sum_{i=1}^{n}\sum_{j=1}^{n}\mathrm{lcm}(a_i,a_j)$。

$$ \begin{aligned} \sum_{i=1}^{n}\sum_{j=1}^{n}\mathrm{lcm}(a_i,a_j)&=\sum_{i=1}^{n}\sum_{j=1}^{n}{\frac{a_i \times a_j}{\gcd(a_i,a_j)}} \\ &=\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{d=1}^{Max}{\frac{a_i \times a_j}{d}[\gcd(a_i,a_j)=d]} \end{aligned} $$

注意到可以把后面的 ∑ 提到前面：

$$ \begin{aligned} \sum_{i=1}^{n}\sum_{j=1}^{n}\mathrm{lcm}(a_i,a_j)&=\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{d=1}^{Max}{\frac{a_i \times a_j}{d}[\gcd(a_i,a_j)=d]} \\ &=\sum_{d=1}^{Max}\frac{1}{d}\sum_{i=1}^{n}\sum_{j=1}^{n}{a_i\times a_j\times [\gcd(a_i,a_j)=d]} \end{aligned} $$

我们注意到 [gcd (ai, aj) = d] 这个式子，这个时候我们想到了什么？没错，莫比乌斯反演！

[k = 1] = ∑d|kμ(d)

但是 [gcd (ai, aj) = d] 这个式子，后面的是 d 而不是 1 ，那我们就把式子变一下形。

$$ [\gcd(a_i,a_j)=d][d|a_i][d|a_j]=[\gcd(\frac{a_i}{d},\frac{a_j}{d})=1][d|a_i][d|a_j] $$

因为我们注意到 d|ai, d|aj 所以就有上面的转化。

$$ \begin{aligned} \sum_{i=1}^{n}\sum_{j=1}^{n}\mathrm{lcm}(a_i,a_j)&=\sum_{d=1}^{Max}\frac{1}{d}\sum_{i=1}^{n}\sum_{j=1}^{n}{a_i\times a_j\times [\gcd(a_i,a_j)=d]} \\ &=\sum_{d=1}^{Max}\frac{1}{d}\sum_{i=1}^{n}\sum_{j=1}^{n}{a_i\times a_j\times [d|a_i][d|a_j][\gcd(\frac{a_i}{d},\frac{a_j}{d})=1]} \end{aligned} $$

之后进行反演

$$ \begin{aligned} \sum_{i=1}^{n}\sum_{j=1}^{n}\mathrm{lcm}(a_i,a_j)&=\sum_{d=1}^{Max}\frac{1}{d}\sum_{i=1}^{n}\sum_{j=1}^{n}{a_i\times a_j\times [d|a_i][d|a_j][\gcd(\frac{a_i}{d},\frac{a_j}{d})=1]} \\ &=\sum_{d=1}^{Max}\frac{1}{d}\sum_{i=1}^{n}\sum_{j=1}^{n}{a_i\times a_j\times [d|a_i][d|a_j]\sum_{t|\gcd(\frac{a_i}{d},\frac{a_j}{d})}}{\mu(t)} \end{aligned} $$

注意到可以和上面一样，所以我们也把 t 的求和往前提。

$$ \begin{aligned} \sum_{i=1}^{n}\sum_{j=1}^{n}\mathrm{lcm}(a_i,a_j)&=\sum_{d=1}^{Max}\frac{1}{d}\sum_{i=1}^{n}\sum_{j=1}^{n}{a_i\times a_j\times [d|a_i][d|a_j]\sum_{t|\gcd(\frac{a_i}{d},\frac{a_j}{d})}}{\mu(t)} \\ &=\sum_{d=1}^{Max}\sum_{t=1}^{\lfloor \frac{Max}{d} \rfloor}\frac{\mu(t)}{d}\sum_{i=1}^{n}\sum_{j=1}^{n}{a_i\times a_j\times [d|a_i][d|a_j][t|a_i][t|a_j]} \\ &=\sum_{d=1}^{Max}\sum_{t=1}^{\lfloor \frac{Max}{d} \rfloor}\frac{\mu(t)}{d}\sum_{i=1}^{n}\sum_{j=1}^{n}{a_i\times a_j\times [dt|a_i][dt|a_j]} \end{aligned} $$

我们来观察后面这个式子 $\displaystyle \sum_{i=1}^{n}\sum_{j=1}^{n}{a_i\times a_j\times [d|a_i][d|a_j]}$ ，对于任何一个 d|a 都会对任何一个 d|B。

注意到 $\displaystyle (\sum_{i=1}^{k}a_i)^2$ 刚好就是 ax(x ∈ [1, k]) 对于所有 ay(y ∈ [1, k]) 都有贡献，所以： $$ \sum_{i=1}^{n}\sum_{j=1}^{n}{a_i\times a_j\times [dt|a_i][dt|a_j]}=(\sum_{i=1}^{n}a_i\times [dt|a_i])^2 $$

$$ \begin{aligned} \sum_{i=1}^{n}\sum_{j=1}^{n}\mathrm{lcm}(a_i,a_j)&=\sum_{d=1}^{Max}\sum_{t=1}^{\lfloor \frac{Max}{d} \rfloor}\frac{\mu(t)}{d}(\sum_{i=1}^{n}a_i\times [dt|a_i])^2 \end{aligned} $$

我们发现 ai 的值域只有 106 ，所以我们可以用 ci 表示有多少个 i，这样就有：

$$ \sum_{i=1}^{n}a_i\times [dt|a_i]=\sum_{dt|i}^{Max}i\times c_i $$

$\displaystyle \sum_{T|i}^{Max}i\times c_i$显然可以用类似筛法的一个东西用 O(nlog(n))的方法求出对于每一个 T 的值。

现在我们的式子变成了：

$$ \sum_{i=1}^{n}\sum_{j=1}^{n}\mathrm{lcm}(a_i,a_j)=\sum_{d=1}^{Max}\sum_{t=1}^{\lfloor \frac{Max}{d} \rfloor}\frac{\mu(t)}{d}(\sum_{dt|i}^{Max}i\times c_i)^2 $$

那么我们只需要枚举 d 再枚举 t 就可以利用 O(nlog(n)) 的时间算出答案。

既然我们已经计算出了 $\sum_{i=1}^{n}\sum_{j=1}^{n}\mathrm{lcm}(a_i,a_j)$ 的值，我们把它减去 $\sum_{i=1}^{n}{a_i}$ ，再除 2（这里取模的话就要用一下逆元），就可以算出 k 了。

算 k 的代码：

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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 998244353;
bool isp[1000000 + 10];
vector<int>prm;
ll n, cnt[1000000 + 5], ans, mu[1000000 + 10], f[1000000 + 10], g[1000000 + 10];
void getprm(int lim) {
	memset(isp, 1, sizeof isp);
	isp[0] = isp[1] = 0;
	mu[1] = 1;
	for (int i = 2; i <= lim; ++i) {
		if (isp[i])
			prm.push_back(i),
			mu[i] = -1;
		for (int j = 0; j < prm.size(); ++j) {
			if (i * prm[j] > lim) break;
			isp[i * prm[j]] = 0;
			if (i % prm[j] == 0) break;
			mu[i * prm[j]] = -mu[i];
		}
	}
	for (ll i = 1; i <= 1000000; i++)
		for (ll j = i; j <= 1000000; j += i)
			f[j] += mu[i] * i;
	for (ll i = 1; i <= 1000000; i++) {
		for (ll j = 1; j <= 1000000 / i; j++) 
			(g[i] += j * cnt[j * i]) %= mod;
	}
}
ll poww(ll x, ll k) {
	if (k == 0) return 1;
	if (k == 1) return x;
	ll tmp = poww(x, k / 2);
	tmp = (tmp * tmp) % mod;
	if (k % 2 == 1) return tmp * x % mod;
	else return tmp;
}
int main() {
	cin.tie(0)->sync_with_stdio(false);
	cin >> n;
	for (ll i = 1, x; i <= n; i++)
		cin >> x, ++cnt[x];
	getprm(1000000);
	for (ll i = 1; i <= 1000000; i++) 
		(ans += i * g[i] % mod * g[i] % mod * f[i]) %= mod;
	for (ll i = 1; i <= 1000000; i++) 
		if (cnt[i]) 
			(ans -= i * cnt[i]) %= mod;
	((ans %= mod) += mod) %= mod;
	(ans *= poww(2, mod - 2)) %= mod;
	cout << ans << endl;
}

设 f(k) 为 k 各个位数上的和，我们要求的 ans 满足 k|ans 且 f(ans) 最小

考虑 dpi 表示 min f(x)(x ≡ i (mod  k))

怎么转移？注意到可以在 x ( x ≡ i (mod  k)) 后加上一个数 y(y ∈ [0, 9]), 那么易得加上后的余数为 (x × 10 + y) mod  k 即 (i × 10 + y) mod  k，所以 dp[(i × 10 + y) mod  k] = min (dp[i] + y)。

注意到这个式子和图的松弛式子很像，接下去就建图确定转移顺序，再跑一遍单源最短路径板子即可，答案即 dis[0]，边是 k 的 10 倍，复杂度为𝒪(𝓀𝓁ℴℊ2𝓀)。

代码：

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 3999971;
bool isp[1000000 + 10];
vector<int>prm;
ll n, cnt[1000000 + 5], ans, mu[1000000 + 10], f[1000000 + 10], g[1000000 + 10];
void getprm(int lim) {
	memset(isp, 1, sizeof isp);
	isp[0] = isp[1] = 0;
	mu[1] = 1;
	for (int i = 2; i <= lim; ++i) {
		if (isp[i])
			prm.push_back(i),
			mu[i] = -1;
		for (int j = 0; j < prm.size(); ++j) {
			if (i * prm[j] > lim) break;
			isp[i * prm[j]] = 0;
			if (i % prm[j] == 0) break;
			mu[i * prm[j]] = -mu[i];
		}
	}
	for (ll i = 1; i <= 1000000; i++)
		for (ll j = i; j <= 1000000; j += i)
			f[j] += mu[i] * i;
	for (ll i = 1; i <= 1000000; i++) {
		for (ll j = 1; j <= 1000000 / i; j++)
			(g[i] += j * cnt[j * i]) %= mod;
	}
}
ll poww(ll x, ll k) {
	if (k == 0) return 1;
	if (k == 1) return x;
	ll tmp = poww(x, k / 2);
	tmp = (tmp * tmp) % mod;
	if (k % 2 == 1) return tmp * x % mod;
	else return tmp;
}
namespace Change {
	struct Edge {
		int v, w, nxt;
	}edge[40000000 + 5];
	int head[4000000 + 5], idx;
	void add(int u, int v, int w) {
		edge[++idx] = { v,w,head[u] };
		head[u] = idx;
	}
	struct node {
		int first, second;
		friend bool operator<(const node& a, const node& b) {
			return a.first > b.first;
		}
	};
	int n, m, k, dis[4000000 + 5];
	priority_queue<node>q;
	bool vis[4000000 + 5];
	void dij() {
		memset(dis, 0x3f, sizeof dis);
		dis[k] = 0;
		q.push({ 0,k });
		while (!q.empty()) {
			node p = q.top(); q.pop();
			if (vis[p.second]) continue;
			vis[p.second] = 1;
			for (int i = head[p.second]; i; i = edge[i].nxt) {
				if (dis[edge[i].v] > dis[p.second] + edge[i].w) {
					dis[edge[i].v] = dis[p.second] + edge[i].w;
					q.push({ dis[p.second] + edge[i].w,edge[i].v });
				}
			}
		}
	}
	void main(int k) {
		for (int i = 0; i < k; ++i)
			for (int j = 0; j < 10; ++j)
				add(i, (i * 10 + j) % k, j);
		for (int i = 1; i < 10; ++i)
			add(k, i % k, i);
		dij();
		cout << dis[0] << endl;
	}
}
int main() {
	cin.tie(0)->sync_with_stdio(false);
	cin >> n;
	for (ll i = 1, x; i <= n; i++)
		cin >> x, ++cnt[x];
	getprm(1000000);
	for (ll i = 1; i <= 1000000; i++)
		(ans += i * g[i] % mod * g[i] % mod * f[i]) %= mod;
	for (ll i = 1; i <= 1000000; i++)
		if (cnt[i])
			(ans -= i * cnt[i]) %= mod;
	((ans %= mod) += mod) %= mod;
	(ans *= poww(2, mod - 2)) %= mod;
	Change::main(ans);
	return 0;
}
#题解 #自己出的题
name 题解
https://lzj-blog.top/2025/02/13/name 题解/
作者
lzj
发布于
2025年2月13日
许可协议