Codeforces Round 856 (Div. 2) B. Not Dividing
给一个长为 \(n\) 的正整数数组 \(a\) ，在一步操作中，你可以选择任一个数并且 \(add\ 1\) 。要求最多执行 \(2n\) 步操作使 \(a\) 满足 \(\forall i, i \in[1, n - 1], a_{i} \nmid a_{i + 1}\) 。输出任一个在操作数限制内可以得到的合法数组。
典一：有关不整除问题，除数中不能有 \(1\) 出现。
- 显然：\(gcd(1, x) = 1\) 恒成立。
典二：若 \(x | y\) ，\(x | y + 1 \iff x = 1\) 。
- 证明：若 \(x | y + 1\) ，则有 \(x | y\) 和 \(x | 1\) 。显然只有 \(x = 1\) 时候成立。
于是先对组中所有 \(1\) 执行 \(add\ 1\) ，这最多会使用 \(n\) 次操作。
然后再次 \(2\) 开始，从左往右扫一遍，若当前位置为 \(x\) 且有 \(a_{x - 1} \mid a_x\) ，因为 \(a_{x - 1} \neq 1\) ，则对 \(a_x\) 执行 \(add\ 1\) 即可。这最多会使用 \(n\) 次操作。