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}
.
{k∗gcd(x,y)|k=1,2,..そしてk∗gcd(x,y)<=y}
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;
}