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$ 的代码：
1 | |
设 $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)}$。
代码：
1 | |