显然每个位置最多操作一次,于是暴力枚举即可,时间复杂度 O(2n)\mathcal{O}(2^n)O(2n)。
无脑 dp 即可,显然在最优解(假设最初所有数的 gcd≠1\gcd \ne 1gcd=1 )中至少有一个位置是操作了的,于是枚举该位置然后在值域上 dp 即可。
多想一想可以发现答案一定不超过 333。
因为 gcd(n−1,n)=1\gcd(n-1,n)=1gcd(n−1,n)=1,所以最坏情况就是把位置 n−1n-1n−1 和 nnn 都操作一遍。
那么就好做了,先检查能不能不操作,再检查能否只操作位置 n−1n-1n−1 或位置 nnn,都不行就输出 333。
使用您的 Hydro 通用账户