首页 > itarticle > poj2348 euclid’s game

poj2348 euclid’s game

admin 1月 18, 2021 0

题解

假设$a>b$。
显然当$amod b=0$时，先手必胜。
当$amod bneq 0$时，若$a>2b$，则可以证明在接下来先手所有可以采取的$k$种策略中必有必胜策略，故这个也是必胜态。
我讲的比较浅显，各位不妨看下《挑战程序设计竞赛》的P310。


#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
using namespace std;
typedef long long ll;
ll a,b,f;
int (){
    for(;;){
        scanf("%lld%lld",&a,&b);
        if(!a&&!b)break;
        f=1;
        for(;;){
            if(a<b)swap(a,b);
            if(a%b==0)break;
            if(a>2*b)break;
            a-=b,f^=1;
        }
        if(f)printf("Stan winsn");
        else printf("Ollie winsn");
    }
    return 0;
}