name 题解

题面描述

给定一个长度为 $n$ 的数列 $a_1, a_2, a_3, \dots, a_n$。

令 $\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)$ 第二个 $\sum$ 不是从 $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}$$

注意到可以把后面的 $\sum$ 提到前面：

$$\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(a_i,a_j)=d]$ 这个式子，这个时候我们想到了什么？没错，莫比乌斯反演！

$$[k=1]=\sum_{d|k}\mu(d)$$

但是 $[\gcd(a_i,a_j)=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|a_i,d|a_j$ 所以就有上面的转化。

$$\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$ 刚好就是 $a_x (x \in [1,k])$ 对于所有 $a_y(y \in [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}$$

我们发现 $a_i$ 的值域只有 $10^6$ ，所以我们可以用 $c_i$ 表示有多少个 $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$ 的代码：

#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)$ 最小

考虑 $dp_i$ 表示 $\min {f(x)}(x\equiv i\pmod k)$

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

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

代码：

#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;
}