2348:Euclid's Game

keyword

互除法　Nim　C++

概要

2つの数a,bがある。プレイヤーはaとbの大きい方から小さい数の何倍かを交互に引いていく。最初に数を0にした方が勝つ。最善を尽くしたとき先手と後手のどちらが勝つか求める問題。
ユークリッドの互除法でgcd(x,y)を呼んだときx/yの値を覚えておけばよい。こうすると一番左の山から1個以上石をとるようなルールのNimに落ちる。石が2個以上あるときは勝つのでこのNimは簡単に解ける。

vector<int> ns;
int gcd(int x, int y){
    if(y==0) return x;
    else{
        ns.PB(x/y);
        return gcd(y,x%y);
    }
}

int solve(int pos, int turn){
    if(pos==SZ(ns)-1) return turn;
    if(ns[pos]>1) return turn;
    else if(ns[pos]==1) return solve(pos+1, -turn);
    else if(ns[pos]==0) return solve(pos+1, turn);
    printf("error\n");
    return 0;
}

int main(){
    int n, m;
    while(scanf("%d%d",&n,&m)){
        if(!(n||m)) break;
        ns.clear();
        gcd(n,m);
        if(solve(0,1)==1) printf("Stan wins\n");
        else printf("Ollie wins\n");
    }
    return 0;
}