Codeforces Round #726 Deleting Divisors 题解 (Java/C++)

题解

我们将数字分成三类：奇数、不包括$2^n$在内的偶数，以及$2^n$。于是，经过一步操作我们发现三类数字会有如下转化：

我们看到，对于奇数，一次操作后，必然变成一个偶数。且我们会发现这个偶数一定不是$2^n$。
显然这奇数的所有因数都是奇数，令这个奇数为$a\cdot b$且$a\cdot b - b=2^x$。则我们会发现$(a-1)\cdot b =2^x$，进而必然有$a-1=2^y$且$b=2^{(x-y)}$。于是与b为奇数矛盾。

对于不是$2^n$的偶数，令这个数为$a\cdot b \cdot c$，其中a为偶数，b为奇数，c为任意数。显然有$a\cdot b \cdot c-b$为奇数，$a\cdot b \cdot c-a$为偶数。

可以看到，如果任何人拿到一个奇数，那么这个人其实没有选择只能将这个数转化为非2的指数的偶数。而恰巧，我们可以注意到对于素数本身一定会导致失败。于是不论是谁，只要拿到了非2的指数的偶数一定会转为奇数。总有一次这个奇数会是一个素数。
所以，如果Alice拿到了非2的指数的偶数，则Alice必胜，否则Bob必胜。

对于$2^n$。因为非2的指数的偶数是必胜状态，因此一定不会向这个方向转化。于是每次都是减去$2^{n-1}$以得到另一个2的指数。于是取决于指数次幂的奇偶性来判断胜负。

综上，对于Alice我们可以得到下面的图：

代码

Java

C++