Codeforces Round#201(Div.2)C数論

4973 ワード

Problem:n(n<=100)個の正数を与え、そこから任意の2つの数を取るたびに、彼らの差が集合になければ集合に加わる.最後の集合の要素の個数のパリティを聞く.Analyse:
  • まず2つの数しかないことを考慮すると,2つの数x,y(x>y)が連続して実行される動作が観察され,生成可能な数の集合は
    {k∗gcd(x,y)|k=1,2,..そしてk∗gcd(x,y)<=y}
  • は、次に3番目の数Zがある場合を考える、先の2つの数、極めて生成された全ての数の最大公約数がgcd(x,y)であるため、3番目の数を加えた後のこの集合の新たな最大公約数はgcd(gcd(x,y),Z)であり、その後生成集合はこの最大公約数の倍数で生成する.
  • ……..
  • はn個の数にまとめられ、最大の数を上界とし、すべてのn個の数の最大公約数で満たされる集合であり、要素の個数は:
    max{xi | 1<=i<=n}gcd{x1,x2,...xn}
    .
  • /**********************jibancanyang************************** *Author* :jibancanyang *Created Time* :   5/10 10:57:35 2016 *File Name* : jy.cpp **Code**: ***********************[email protected]**********************/
    
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <queue>
    #include <set>
    #include <map>
    #include <string>
    #include <cmath>
    #include <cstdlib>
    #include <ctime>
    #include <stack>
    using namespace std;
    typedef pair<int, int> pii;
    typedef long long ll;
    typedef unsigned long long ull;
    vector<int> vi;
    #define pr(x) cout << #x << ": " << x << " " 
    #define pl(x) cout << #x << ": " << x << endl;
    #define pri(a) printf("%d
    ",(a));
    #define xx first #define yy second #define sa(n) scanf("%d", &(n)) #define sal(n) scanf("%lld", &(n)) #define sai(n) scanf("%I64d", &(n)) #define vep(c) for(decltype((c).begin() ) it = (c).begin(); it != (c).end(); it++) const int mod = int(1e9) + 7, INF = 0x3fffffff; const int maxn = 1e5 + 13; int gcd(int a, int b) { if (!b) return a; return gcd(b, a % b); } int main(void) { int n; while (cin >> n) { int x = 0; cin >> x; int g = x; for (int i = 1; i < n; i++) { int y; cin >> y; x = max(y, x); g = gcd(g, y); } if ( (x / g - n) % 2) cout << "Alice" << endl; else cout << "Bob" << endl; } return 0; }