Chlience

【题解】HDU 1525 Euclid's Game
Problem给定两个整数 $n,m$ ,两人依次操作,每次可以将较大的数减去较小的数的正整数倍,其差只能为非负数...
扫描右侧二维码阅读全文
20
2019/02

【题解】HDU 1525 Euclid's Game

Problem

给定两个整数 $n,m$ ,两人依次操作,每次可以将较大的数减去较小的数的正整数倍,其差只能为非负数
当较小数为 $0$ 时,游戏结束,无法操作者失败

Thought

假设当前的数 $a,b$ ,其中 $a>b$

当 $a\ge2*b$
若 $(b,a\bmod b)$ 是后手必胜状态,那么先手可以转移到 $(b,a \bmod b)$
若 $(b,a\bmod b)$ 是先手必胜状态,那么先手直接转移到 $(a\bmod b+b,b)$ ,后手则只能转移到 $(b,a \bmod b)$ ,即先手必胜状态

当 $a<2*b$
显然只能转移到 $(b,a-b)$ ,直接递归往下做即可,可以证明在 $\log$ 的时间内可以解决

Code

#include <vector>
#include <queue>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
int gcd(int a, int b, int c) {
    if(a < b) swap(a, b);
    if(!b) return c;
    if(a >= 2 * b) return c ^ 1;
    return gcd(b, a % b, c ^ 1);
}
int main() {
    while(1) {
        int n = read(), m = read();
        if(!n && !m) break;
        puts(gcd(n, m, 0) ? "Stan wins" : "Ollie wins");
    }
    return 0;
}
Last modification:February 20th, 2019 at 08:32 am

Leave a Comment