CodeForces 346A Alice and Bob (数学最大公约数)

题意：有一堆数，然后有两个人轮流从中取出两个数，这两个数的差的绝对值不在这个集合，然后把这个数放进这个集合，如果哪个人不能拿了，就是输了，问你谁赢。

析：当时连题意都没看好，以为拿出两个数，就不放回了，如果好好分析第三组样例，就不会看成这样了。

思路应该是这样的，既然是拿了再放差的绝对值放进去，那么最后肯定会形成一个等差数列的，想想对不对，可以写几个试试，那么然后除以最大公约数，就能形成一个1-最大数的

等差队列，最大数就是输入的最大数，因为两个正数作差，肯定比最大的小。那么答案就有了。

代码如下：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn = 1e2 + 5;

int a[maxn];

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

int main(){

    int n;

    cin >> n;

    for(int i = 0; i < n; ++i)  cin >> a[i];

    sort(a, a+n);

    int g = a[0];

    for(int i = 1; i < n; ++i) g = gcd(g, a[i]);

    int ans = a[n-1] / g - n;

    if(ans & 1)  puts("Alice");

    else  puts("Bob");

    return 0;

}

巴特西

CodeForces 346A Alice and Bob (数学最大公约数)

最新文章

热门文章