做题笔记 - 数论

交换余生(SCCPC 2026)

我印象中我可能很久以前做过原题，但是忘了。但思路挺直接的。

即序列重排后要求每一个前缀 $⁡\gcd$ 和对应后缀的 $⁡\gcd$ 不能相同。

先把数组的最大公约数降成 $1$，不失一般性。否则可能会干扰后续操作。

不难发现前缀 $\gcd$ 必然单调不增，后缀单调不减。由于不可能出现一个 $d\gt 1$ 使得存在一个前缀和对应后缀使得 $⁡\gcd$ 均为 $d$（这样的话就意味着序列 $⁡\gcd$ 恰好为 $d$ 了），所以存在不满足题目条件的情况只能是至少存在一个前缀和对应后缀 $\gcd$ 恰好为 $1$。

对于一个合法的序列，前段有一个公约数 $d_1\gt 1$，后段有一个公约数 $d_2\gt 1$。所有元素中最多只能存在一个元素同时不能被 $d_1,d_2$ 整除，放在序列中间，如果可以被 $d_1$ 整除放在前段，如果可以被 $d_2$ 整除放在后段。对于 $d_1$ 可以枚举 $a_1,a_2$ 所有因数 $d_1$ 做判断（若存在合法序列，则 $a_1,a_2$ 中至少有一个能被 $d_1$ 整除）。每次判断的时候筛掉每一个不能被 $d_1$ 整除的元素，在剩下的序列里面用同样的方法枚举 $d_2$ 再次筛掉同样不能被 $d_2$ 整除的元素判断剩下的元素个数是否小于等于 $1$。若可以，说明中段存在放 $1$ 个同时不能被 $d_1,d_2$ 的元素的方案，否则不行。

Increment All Divisors

难度：1911

我怎么一道 AtCoder 蓝题都做了 3h 啊，我是不是要完蛋了。

令每个元素要到达的值为 $T$，在第 $i$ 个元素上操作的数量为 $f(i)$。则有：

$$T=A_i+\sum_{1\le j\le \lfloor\frac{n}{i}\rfloor}f(ij)$$

。令 $g(i)=\sum_{1\le j\le \lfloor\frac{n}{i}\rfloor}f(ij)$，则有：

$$g(i)=T-A_i$$

。由莫比乌斯反演可得：

$$f(i)=\sum_{1\le j\le \lfloor\frac{n}{i}\rfloor}g(ij)\mu(j)$$

。显然，我们得到的 $f(i)$ 是关于 $T$ 的一次函数形如 $f(i):y=k_iT+b_i$。注意到这里的 $f(i)$ 需要满足非负，所以即要求若干个不等式组 $k_iT+b_i\ge 0$。分讨一下 $k_i$ 的正负性可以得到 $T$ 的范围。

注意到每一次操作都会使 $A_1$ 变化 $1$，所以题目要我们求的实际上是 $g(1)=T-A_1$。当 $T$ 取最小值时可以得到最优解。