Codeforces Round #752 (Div. 2) ABCDE 题解 (Java/C++)

A. Era

模拟即可。当我们发现某一个a[i]>i+ ans时，插入a[i]-(i+ ans)个数即可。

Java

C++

如果是n是一个偶数，那么我们以一个数为一个子串。这样就是偶数个1做XOR操作，其结果必然为0。

如果n是一个奇数，类似的，我们寻找$a[i]\geq a[i+1]$，这样把这两个数放在一起时，就又是偶数个1取XOR。

Java

C++

显然的，a[1]必须不能被2整除，否则一定是NO。因为a[1]没有办法通过删除前面的数来删除。同理a[2]至少能不被2或3中的一个整除。以此类推。

同时，我们注意到，如果一个数能被2到x之间的所有数整除，那么这个数一定能被2，3，…，x的最小公倍数整除。
因此我们只需要求出这个x，使得$lcm(2,3,\dots,x)>10^9$。

只要a[i]能被2到min(x, i)之间有一个数不整除即可。如果都整除就输出NO。

Java

C++

根据x和y的大小关系，由以下几种情况：

如果x>y，那n=x+y即可。此时n mod x = y mod n = y。
如果x=y，n=x即可。
如果y>x且y mod x = 0。那n=x即可。此时n mod x = y mod n = 0。
如果y<x且y mod x $\neq$ 0。此时，我们注意到x和y都是偶数。那很自然的，$n=\frac {\left \lfloor \frac y x \right \rfloor \cdot x + x} 2$。