天才和疯子互相为邻

「AGC010D」Decrementing

发表于 分类于

$Link$

黑板上有 $n$ 个数$a_{1\cdots n}$，它们的 $\operatorname{gcd}=1$。$A$ 跟 $B$（$A$ 先手）轮流进行以下的操作，操作共两步如下：

  • 选择一个数，把它 $-1$
  • 把黑板上所有数除以它们的 $\operatorname{gcd}$。

问如果两人都采取最优策略，谁会赢。

$1\le n\le10^5,1\le a_i\le10^9$。

先不考虑第二步操作，如果只有第一步操作，显然答案只与 $sg=-n+\sum_{i=1}^n a_i$ 的奇偶性有关。

同样，如果序列的 $\operatorname{gcd}$ 一直等于 $1$，也就相当于没有第二步操作。

容易得到，除非序列的 $\operatorname{gcd}=2$，否则 $sg$ 的奇偶性均不变。

那，如果 $sg$ 是奇数，先手只要一直让序列的 $\operatorname{gcd}\not=2$ 即可。

由于一开始的 $\operatorname{gcd}=1$，所以序列中至少有一个奇数，至于 $n=1$ 的情况，特判掉即可。

又因为 $sg$ 是奇数（即序列中有奇数个偶数），先手只要不断把偶数（包括后手制造出的）变成奇数就可以保证序列中不会没有奇数，也即 $\operatorname{gcd}=1$。

因此序列中有奇数个偶数时先手必胜。

否则，如果 $sg$ 是偶数（即序列中有偶数个偶数），先手想要赢必须要让序列的 $\operatorname{gcd}=2$ 才能使得 $sg$ 的奇偶性有可能转化。

如果序列中有大于一个奇数，那么先手就算不断把奇数变成偶数，后手只要把它再变回来即可，此时后手必胜。

如果只有一个奇数？那先手把它变成偶数约掉 $\operatorname{gcd}$，不断递归下去即可，要注意此时先后手有一个交换。显然这个层数是 $\log a_i$ 级别的。

时间复杂度 $O(n\log a_i)$。

$code$

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
inline int read()
{
    int f = 1, x = 0;
    char ch;

    do{
        ch = getchar();
        if (ch == '-')
            f = -1;
    }while(ch < '0' || ch > '9');
    do{
        x = x * 10 + ch - '0';
        ch = getchar();
    }while(ch >= '0' && ch <= '9');
    return f * x;
}
const int N = 1e5;

int n;
int a[N + 1];

inline int gcd(int x, int y)
{
    if (!y)
        return x;
    return gcd(y, x % y);
}
inline int check()
{
    int sum = 0;
    bool flag = false;

    for (int i = 1; i <= n; i++) {
        if (a[i] == 1)
            flag = true;
        if ((a[i] & 1) == 0)
            sum++;
    }
    if (sum & 1) {
        return 1;
    } else {
        if (flag)
            return 2;
        if (sum == n - 1) {
            int g;
            if (a[1] & 1)
                g = a[1] - 1;
            else
                g = a[1];
            for (int i = 2; i <= n; i++)
                g = gcd(g, a[i] & 1?a[i] - 1:a[i]);
            for (int i = 1; i <= n; i++)
                a[i] /= g;
            return check() == 1?2:1;
        } else {
            return 2;
        }
    }
}
int main()
{
    n = read();
    for (int i = 1; i <= n; i++)
        a[i] = read();
    if (n == 1) {
        printf("%s\n", a[1] == 1?"Second":"First");
        return 0;
    }

    printf("%s\n", check() == 1?"First":"Second");

    return 0;
}