首页 > 代码库 > hdu1525 Euclid's Game , 基础博弈

hdu1525 Euclid's Game , 基础博弈

2024-07-18 21:11:28   218人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=1525
题意：
两人博弈，给出两个数a和b，

较大数减去较小数的任意倍数，结果不能小于0，将两个数任意一个数减到0的为胜者。


题解：
假设a大于b

a == b.  N态
a%b == 0. N态
a >= 2*b，先手能决定谁取(b,a%b),并且知道(b,a%b)是P态还是N态.    N态

b<a<2*b, 只能 -->(b,a-b) , 然后再进行前面的判断.


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

int main() {
    int a, b;
    while(scanf("%d%d", &a, &b))
    {
        if(a==0&&b==0) break;
        if(a<b)  swap(a,b);
        bool Stan = true;
        while(1)
        {

            if(b==0 ||a%b==0||a/b>=2) break;
            int t = a;
            a = b;
            b = t - a;
            Stan = !Stan;
        }
        if(Stan) printf("Stan wins\n");
        else printf("Ollie wins\n");
    }
    return 0;
}



联系
我们