Codeforces Beta Round #90 A: Epic Game

Codeforces

問題概要

ふたりのプレイヤーがゲームをする。それぞれある値A,Bを持っている。今、山にN(<100)個の石がある。各プレイヤーは交互に山からgcd(X, Y)(Xは自分の持っている値、Yは今山にある石の個数)だけ石を取り除く。石を取り除くことができなくなった方の負け。どちらが勝つか判定する問題。

考えたこと

  • いつも思うけど、こういうのはゲームと言わないと思う。あえて言うなら作業ゲー。
    • とはいえ、そう書かれていた方が問題文は理解しやすいのだけど。
  • シミュレーションするだけ。

本番で通ったコード

計算量O(N*log N)くらい？忘れがちだけど、gcdの計算量はlog。

#include <cstdio>
#include <algorithm>
using namespace std;

int N, A, B;

int solve(){
	int turn = 1;

	for(;;){
		if(N == 0){
			break;
		}
		if(turn){
			N -= __gcd(A, N);
		}
		else{
			N -= __gcd(B, N);
		}
		turn = 1 - turn;
	}

	return turn;
}

int main(){
	scanf("%d%d%d",&A,&B,&N);

	printf("%d\n", solve());
	return 0;
}

for(;;)と書くくらいならwhile(N>0)の方がよかった気もする。