打的依托还能涨 Rating 也是神人了
A
直接依照题意做，求个前缀和后对每个 \(s _ i = 1\) 判断前面 \(k - 1\) 个数的和是否大于 \(0\)，都是 \(0\) 就保护。
B
我们一定要让 \(a _ i(i \bmod 2 = 0)\) 越大越好，而变大的方式只有操作 \(1\)，于是我们先对每个偶数的位置进行一次操作 \(1\)，然后对于每个奇数的位置算出要操作多少次才能使其合法，加起来就对了。
C1
发现答案一定不超过 \(2\)，因为我们一定能在 \(2\) 次操作内使得两个数都被 \(2\) 整除。
以下的因数忽略 \(1\)。
那我们考虑怎么判断答案为 \(0\) 或者 \(1\)。枚举 \(i \in [1,n]\)，先判断 \(a _ i + 1\) 的因数是否在前面出现过，出现过则答案为 \(1\)，然后判断 \(a _ i\) 的因数是否在前面出现过，出现过则答案为 \(0\)，然后添加自己的所有因数。这只考虑到了 \(i \gt j\) 的情况，还有 \(i \lt j\) 的情况，这种情况我们可以倒着再做一遍。
时间复杂度 \(\Omicron(n \sqrt{N})\)。
C2
现在我们多了一种情况，也就是仅对一个数操作多次。我们一定不会对两个数同时操作大于 \(2\) 次，否则一定可以在 \(2\) 次以内使得两个数都可以被 \(2\) 整除。我们一定会操作 \(b\) 最小那个使得与后面某个值有共同的质因数。
考虑优化上面的方法，我们发现我们不一定要枚举所有因数，只需要枚举质因数就行。小于等于 \(N\) 的数的所有质因数可以用埃氏筛在 \(\Omicron(N \log \log N)\) 的复杂度内预处理出。这样 C1 的复杂度就下降到 \(\Omicron(n \omega(\max \{ N \}))\)。加入了 \(b\) 的限制之后答案初始值为最小的两个 \(b\) 的值之和，然后就做完了。
时间复杂度 \(\Omicron(n \omega(N) + N \log \log N)\)，略微卡常。