给你一个数字n,对于n若存在因数a(a不等于1或n),则可以将n替换为n-a
现在alice和bob轮流对这个数进行操作,如果一方无法操作则另一方胜利.求在双方采取最优策略的情况下,最终获胜的一方是谁?
此时可以将其写成n=a\times{}b,其中a和b都是奇数;
如果Bob选择每一手都重复Alice的操作,那么两轮过后会变成n=(a-2)\times{}b或者n=a\times{}(b-2),显然此时的n依然是奇数.
根据数学归纳法易知,若n为奇数(奇合数)则可以转化成1\times{}1.
3.若n为偶数(非2的幂次)
此时一定可以将其写成n=a\times{}b,其中a是偶数b是奇数.
Alice先手减去一个b,使之成为n=(a-1)\times{}b,其中a-1和b都是奇数,转化为2中的情况(Alice后手,必胜)
在n为偶数时,有一种情况无法写成3中形式,即n为2的幂次.
因此,当i为偶数时,Alice胜;当i为奇数时,Bob胜.
is_output=1;