P1408 题解

feecle6418 · 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 即可。