Codeforces #201 Div1. A. Alice and Bob

CF201は参加してA,Bでpretest通したものの、Bはsystest通せず。
幸いHackを1個成功していたのでレートは落ちずに済んだ。
http://codeforces.com/contest/346/problem/A

問題

自然数N個からなるdistinctな数列Aが与えられる。
ここで2人でゲームを行い、交互に数列Aに対して以下の処理を行う。

• 数列Aの任意の2要素x,yについて|x-y|が数列A中にないなら、|x-y|をAに加える。

上記処理ができなくなった方が負けである。
2人が最適手を取った場合の勝者を答えよ。

解法

まずAの最大公約数を求め、それでAの各要素を割る。
すると、Aの最大公約数は1となる。
最大公約数は1ということは、|x-y|をとる作業を繰り返すといずれ1が生成できることになる。
また、いったん1が生成されれば、Aの最大要素から1ずつ引くことで1～最大要素のすべてが生成できる。
よって、最大要素の値から、Aの要素数を引いたものが取れる手の数であり、その偶奇で勝者が決まる。

int N;
int A[1001];
int gcd(int a, int b) { return (b==0)?a:gcd(b,a%b);}

bool solve2() {
	int f,r,i,j,k,l,x,y,tx,ty;
	int g=A[0];
	for(i=1;i<N;i++) g=gcd(g,A[i]);
	FOR(i,N) A[i]/=g;
	return ((A[N-1]-N) % 2)==1;
}
void solve() {
	int i;
	cin>>N;
	FOR(i,N) cin>>A[i];
	sort(A,A+N);
	if(solve2()) _P("Alice\n");
	else _P("Bob\n");
}

まとめ

Aとしてお手頃な面白い問題。