题解 AT2305 【[AGC010D] Decrementing】

xcyle · 2021-01-03 15:04:06 · 题解

首先，如果a_i中有1那么双方能做的操作只有-1，此时胜负已经由\sum a_i-1的奇偶性决定

我们再考虑除以最大公因数这个操作，双方会根据上式的奇偶性变化来决策自己的操作，因此我们的关注点应该在奇偶性上。奇公因数是不会改变其局势的

那么我们考虑，如果初态为奇，那么这时候看上去是先手必胜的，因此先手一定会努力维持住这个局面，只要最大公因数一直为1，先手就能将优势持续到最后

我们会发现，先手一步可以将偶数变成奇数，因此新的局面一定不会出现偶公因数。之后的策略也是相同的。因此，如果初态为奇，先手必胜。

然而初态为偶呢？先手必定会努力改变奇偶性，因为一旦在第一步没有改过来，后手将会像刚才那样掌控全局。然而先手一次只能操作一个数，如果操作后有偶公因数，原来的局面只会有一个奇数，并且先手会操作它

在此博弈思想的指导下，我们会发现一个局面除非可以一步判断最终的胜负，先手的操作必然是唯一的

我们在分析一下时间复杂度，每次每个数除以2，最多只会操作log次，总时间O(nlog^2a)

#include <iostream>
#include <cstdio>
#define maxn 100005
using namespace std;
int n, a[maxn];
inline int gcd(int x, int y)
{
    if(x < y) swap(x, y);
    return y == 0 ? x : gcd(y, x % y);
}
int work()
{
    int sum = 0;
    for (int i = 1; i <= n; i++)
    {
        sum += a[i] - 1;
    }
    if(sum & 1) return 1;
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        if(a[i] & 1) cnt++;
    }
    if(cnt > 1) return 0;
    for (int i = 1; i <= n; i++)
    {
        if(a[i] & 1)
        {
            if(a[i] == 1) return 0;
            a[i]--;
        }
    }
    int d = a[1];
    for (int i = 2; i <= n; i++)
    {
        d = gcd(d, a[i]); 
    }
    for (int i = 1; i <= n; i++)
    {
        a[i] /= d;
    }
    return (work() ^ 1);
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]); 
    }
    if(work()) printf("First");
    else printf("Second");
    return 0;
}