自动搬运

查看原文

来自洛谷，原作者为

	feecle6418 **

搬运于2025-08-24 21:24:44，当前版本为作者最后更新于2023-02-08 11:55:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

不妨假设对 $i,i+1$ 执行了一次操作，且操作的公因数 $d$ 不是质数，则它可以分解为两个大于 $1$ 的正整数的乘积 $p\times q$；因为 $p,q\ge 2$ 所以 $pq\ge p+q$，那不如分别去操作 $p,q$。所以，每次操作都操作一个质数更优。

把每个数分解质因数，对每个质数分开考虑它的幂次的变化，相当于：每次可以把相邻两个数均减去 $1$，问最小的操作次数使得任意相邻两个数均不同时 $\ge 0$，这个从左往右做个 dp 即可。