G-涂色博弈 博弈问题 GCD

G-涂色博弈

Problem Description

小明和小红正在玩一个涂色游戏，游戏是这样的：

有n个空格子，第i个空格子的标号是i，

一开始a号格子和b号格子已经涂色，

两名玩家轮流选择一个空白格子涂色，

但如果要选择格子x，要求场上存在已涂色的格子y和z，满足x=y-z或x=y+z。

如果某一轮谁无法涂色，那么就输了。

为了彰显自己的信心，小明决定先手涂色！

请你猜猜在双方都采取 最优策略 的情况下，谁会获胜！

如果小明能够胜利，输出Yuwgna。

如果小红能够胜利，输出Iaka。

Input

第一行输入一个数 T (T <= 500) 代表着将要测试的样例数。

每组数据给定n,a,b（n<=2e4，a,b,<=n)

Output

对于每组数据，输出Yuwgna或者Iaka。

Sample Input

16
2 1 2
3 1 3
67 1 2
100 1 2
8 6 8
9 6 8
10 6 8
11 6 8
12 6 8
13 6 8
14 6 8
15 6 8
16 6 8
1314 6 8
1994 1 13
1994 7 12      

Case #1: Iaka
Case #2: Yuwgna
Case #3: Yuwgna
Case #4: Iaka
Case #5: Iaka
Case #6: Iaka
Case #7: Yuwgna
Case #8: Yuwgna
Case #9: Iaka
Case #10: Iaka
Case #11: Yuwgna
Case #12: Yuwgna
Case #13: Iaka
Case #14: Yuwgna
Case #15: Iaka
Case #16: Iaka      

题目分析

AC Code

#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b){ return b == 0 ? a : gcd(b, a % b); }

int main(){
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++){
        int a, b, n;
        cin >> n >> a >> b;
        int flag = n / gcd(a, b);
        if (flag % 2 == 0) printf("Case #%d: Iaka\n", i);
        else printf("Case #%d: Yuwgna\n", i);
    }
    return 0;
}