题意
两个人互相玩,他们先搞一个集合,里面几个不同的数,接下来随便挑俩作差,如果差的绝对值集合里没有,就给这个差的绝对值加进去,直到集合加不进去值为止,没招的那位就跪了。
思路
写几个数模拟一下就会发现,游戏结束时,集合里面是所有的初始几个值的最大公约数的倍数,举个例子init={2,6,8},gcd=2,final={2,4,6,8},利用这个规律我们就可以知道最终集合有几个元素,最终元素个数减去初始元素个数就是这场比赛将在多少手之后结束,接下来判断奇偶就可以判断谁赢了。
接下来上代码
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 |
#include <iostream> #include <vector> using namespace std; long long gcd(long long a,long long b){ if (b == 0) { return a; } return gcd(b, a%b); } long long lcm(long long x,long long y){ return x*y/gcd(x, y); } int main(){ int n = 0; cin >> n; long long maxn = 0; long long g = 1; cin >> maxn; g = maxn; for (int i = 1; i <= n-1; i++) { long long tmp = 0; cin >> tmp; maxn = max(maxn,tmp); g = gcd(g,tmp); } if ((maxn/g - n)&1) { cout << "Alice" << endl; }else{ cout << "Bob" << endl; } return 0; } |