HDU5512

标签：gcd int HDU5512 定理 define 裴蜀 cout

本题考察裴蜀定理，刚刚学过就写了一下。能够维修的塔就是\(a,b,a-b,a+b,a+2b,a-2b,2a-b,2a+b...\)，上述这些塔的位置就符合ax-by的格式，也就是可以使用裴蜀定理了。裴蜀定理为\(ax+by=gcd(a,b)\)，也就是说上述的所有能够维修的塔的位置都是\(gcd(a,b)\)的整数倍即为\(n/gcd(a,b)\)。那么如果这个数如果是奇数，那么就是先手的赢，“Yuwgna”win；反之“Iaka”win。

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define buff ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define ll long long
#define int ll
const int N = 2e5 + 7;
int cnt = 1;

void solve()
{
    cout << "Case #" << cnt << ": ";
    int n, a, b;
    cin >> n >> a >> b;
    cout << (n / gcd(a, b) % 2 == 0 ? "Iaka" : "Yuwgna") << endl;
    cnt++;
}

signed main()
{
    buff;
    int tt = 1;
    // cin >> tt;
    while (tt--)
    {
        solve();
    }
    return 0;
}

标签：gcd,int,HDU5512,定理,define,裴蜀,cout
From： https://www.cnblogs.com/LANSGANBS/p/18400541