arc137

a:
有点神经
首先贪心让y尽可能大,x尽可能小，那么我们用两层循环，y从大往小枚举，x从小往大枚举，再大力剪下枝，根据质数的稠密性，这个复杂度是有保证的。不过自己的感觉也大差不差
by 官方

自 \(\gcd(L,L+1)=1\) 起，总有一个解。

我们只需按 \((y-x)\) 的递减顺序尝试 \(L \leq x , y \leq R\) 的所有配对 \((x,y)\) ，并在得到 \(\gcd(x,y)=1\) 时打印 \((y-x)\) 。

这种方法的正确性显而易见，让我们来估算一下其复杂性。我们将尝试 \(O(K^2)\) 对，其中 \(K\) 是 \(R-L\) 与答案的差。考虑到计算 gcd 所需的时间，总复杂度为 \(O(K^2 \log R)\) ，因此如果我们能证明 \(K\) 是小数，那么我们就完成了。

一种证明方法是使用 素数差距。

在这个问题的约束条件下， \(1500\) 连续整数总是包含至少一个素数。因此，在 \((x,y)=(L,R),(L,R-1),\cdots,(L,R-1500)\) 中，至少有一个满足 \(\gcd(x,y)=1\) 。由此可见 \(K \leq 1500\) 。

提交示例（C++）

事实上， \(K\) 会比这个极限小得多。在 \(R-5, \cdots, R\) 中，总有一个数与 \(30\) 共乘，而在约束条件下，这个数总是与 \(L, \cdots, L+16\) 中的某些数共乘。这就证明了 \(K \leq 21\) 。(由 maspy 证明)使用 CRT 可以生成有 \(K=7\) 的情况。(洗素数的想法是由 Nyaan 提出的)。

b:
发现能弄出来的1数量是连续的，所以我们输出最多能增加多少1或最多能减少多少1就可以了。用最大子段和即可。

c:
trick写在博弈论的题解里了。

由于a[n]>a[n-1]+1为必胜态，那么我们alice就不能给bob丢这个态，所以每次都会保证数连续地取。所以数组中最大的数都会减少1，所以最终次数是a[n]-(n-1)，判断奇偶即可