Luogu P1290 – 博弈论

PROBLEM

https://www.luogu.org/problemnew/show/P1290

ANALYSIS

第一次取得a/b>1 的人会取得胜利。

感觉就是一个思考题。

SOLUTION

#include <bits/stdc++.h>

using namespace std;

//return 1 if Stan wins
int gcdt(int a, int b) {
    bool layer = 0;
    int t;
    if (a < b) {
        swap(a, b);
    }
    while (a % b != 0) {
        layer ^= 1;
        if (a / b != 1) {
            return layer;
        }
        t = b;
        b = a % b;
        a = t;
    }
    return !layer;
}

int a, b;

int main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> a >> b;
        cout << (gcdt(a, b) ? "Stan wins" : "Ollie wins") << endl;
    }
    return 0;
}

本作品使用基于以下许可授权：Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.