Codeforces Round #201 (Div. 2)

题目链接：http://codeforces.com/contest/347/problem/C

题意是给你一个数n，然后n个数，这些数互不相同。每次可以取两个数x和y，然后可以得到|x - y|这个数，要求不在这个数组中，然后添加进去，直到不能取为止，不能取的人输了。Alice先取，求谁最后能赢。

可以先列举几种情况，可以发现，一般情况取到最后剩下1~max这些数了。但是要是比如原来的数有3 12这两个数，那最后就会剩下3 6 9 12这4个数，由此可以看出这种情况下剩下的一定是原来数的gcd的倍数，所以答案就是Max/gcd - n。

 #include <iostream>

 using namespace std;

 int a[];

 int gcd(int x , int y) {

     if(!y) return x;

     return gcd(y , x % y);

 }

 int main()

 {

     int n , temp , Max = -;

     cin >> n;

     for(int i =  ; i <= n ; i++) {

         cin >> a[i];

         Max = max(Max , a[i]);

     }

     temp = gcd(a[] , a[]);

     for(int i =  ; i <= n ; i++)

         temp = gcd(temp , a[i]);

     if((Max / temp - n) & )

         cout << "Alice\n";

     else

         cout << "Bob\n";

 }

巴特西

Codeforces Round #201 (Div. 2) - C. Alice and Bob

最新文章

热门文章