题目地址，一道R1700的题目

一句话题意

给定正整数nn，每次可以对其做如下操作：将当前的nn减去它的除了11和nn以外的因子得到新的nn

现在Alice和Bob轮流操作，Alice先手，不能操作者输。

tt组询问，每组询问给定nn，如果两人都以最佳策略操作，问谁能胜出。

解法

可以分为以下三种情况讨论：

  1. nn为奇数
  2. nn为偶数，但不是22的幂
  3. nn是22的幂

考虑第1种情况。由于nn是奇数，那么它的任一因子kk也一定是奇数，而kk又一定是n−kn-k的因子，所以n−kn-k是偶数，但不是22的幂（情况2）。这是情况1唯一可行的操作。

考虑第2种情况。显然nn存在一个奇因子。一种可行的操作是对nn减去它的一个奇因子，得到一个奇数（情况1）。

我们知道，当nn为质数是必败态，因为质数的因子只有11和它本身。而质数要么是22（212^1），要么是一个奇数（情况1）。

若当前玩家面临情况2，可以用之前提到的方法将另一个玩家面临的情况转化为情况1.而另一玩家只能将情况1转化为情况2.由于游戏一定会在有限步内结束，所以面临情况1的玩家最终一定会遇到一个质数，情况2是一个必胜态，而情况1是一个必败态。

再来考虑第3种情况。有两种可行的操作：令nn折半（若n=2kn=2^k，则n′=2k−2k−1=2k−1n'=2^k-2^{k-1}=2^{k-1}，仍为情况3），或是减去一个其他22的幂。第二种操作会使得另一玩家面临情况2，即必胜态，所以不可能采取第二种操作。于是kk为奇数时为必败态，kk为偶数时为必胜态。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <map>
using namespace std;
typedef long long ll;

template<typename T>void read(T &t)
{
    t=0;int f=0;char c=getchar();
    while(!isdigit(c)){f|=(c=='-');c=getchar();}
    while(isdigit(c)){t=t*10+c-'0';c=getchar();}
    if(f)t=-t;
}

const int maxn=500000+100;
int T;
int n;
char s[maxn];

int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}

int Checkpow2(int x)
{
    int re=0;
    while(x%2==0)
    {
        ++re;
        x/=2;
    }
    return x==1?re:0;
}

void Work()
{
    read(n);
    int K=Checkpow2(n);
    if(K!=0)
        printf(K%2?"Bob\n":"Alice\n");
    else
        printf(n%2?"Bob\n":"Alice\n");
}

int main()
{
    read(T);
    while(T--)
    {
        Work();
    }
    return 0;
}

感想

比起解法，我更关心的是怎么想到这样分类的？

现在遇到跟因数有关的问题都会先往质因数分解的方向去靠，然后一般就会吃瘪，特别是需要处理加减操作的时候

功力尚浅啊