Alice and Bob CodeForces - 347C （博弈）

题目

https://vjudge.net/problem/CodeForces-347C

题意

给你一个长度为n的序列。Alice先动，选择序列中随便的两个数，求他们差的绝对值。如果和序列的数不重复就加入序列。如果找不到这样的两个数就算输

思路

做差的过程可以看做辗转相减就GCD，所以最后所有数为n个数的最大值除以gcd

那么产生新数个数就可以知道，如果是奇数，先手赢，如果是偶数，后手赢

代码

#include <bits/stdc++.h>using namespace std;
const int maxn = 1e5+100;
int a[maxn];
int main()
{int n;while(scanf("%d",&n) != EOF){int MAX = 0;for(int i = 1;i <= n;i++){scanf("%d",&a[i]);MAX = max(MAX,a[i]);}int k = a[1];for(int i =2;i <= n;i++){k = __gcd(k,a[i]);}int ans = MAX /k-n;if(ans % 2 ) printf("Alice\n");else printf("Bob\n");}return 0;
}