Codeforces Round #114 (Div. 1) C : Wizards and Numbers

Codeforces

問題概要

ふたつの数A,B(A<=B)に対して

  1. BからA^k(k>0)を引く。
  2. BをB%Aで置き換える。

のいずれかの操作を施す。どちらかが0の状態で自分の番になったら負ける。勝つのが先手か後手か判定する問題。A,B<10^18、テストケース数10^4。

解法

(B%A, A)が負けの状態であるとき、その状態に遷移できるので(A,B)は勝ちである。(B%A, A)が勝ちの状態であるとき、どちらのプレイヤーも(B%A, A)に遷移しないようにしなければならない。
したがってBからAのべきを引くしかないのだが、BがAより小さくなったらそれは必ず(B%A, A)という状態である。何故ならBから引く数は必ずAの倍数だからである。
結局、BからA^k(k>0)を何回引くことができるか、というゲームに帰着される。これはk>=0であればSRM PotateGameなどで見た有名問題そのものである。この問題はk>0となっているが、BをB/A+1で考えればk>=0で考えるのと同じことになる。したがってB/A+1をk+1で割った余りを見てやればよい。
こんなん言われてやっと気づくレベル…。

acceptされたコード

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

typedef long long int64;

int64 A, B;

void init(){
	cin >> A >> B;
}

bool rec(int64 A, int64 B){
	if(A == 0 || B == 0){
		return false;
	}
	if(A > B){
		swap(A, B);
	}
	if(!rec(B%A, A)){
		return true;
	}
	return ( (B/A)%(A+1) )%2 == 0;
}

int main(){

	int T;
	cin >> T;
	for(;T--;){
		init();
		puts(rec(A, B) ? "First" : "Second");
	}

	return 0;
}