救救孩子吧
查看原帖
救救孩子吧
872662
mengleo楼主2024/10/1 20:38
#include <bits/stdc++.h>
#define int long long
#define endl "\n"

using namespace std;

int t, a, b, c, x, y;

int exgcd(int a, int b)
{
    // if(a < b)
    // {
    //     swap(a, b);
    // }
    if(b == 0)
    {
        x = 1;  
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b);
    int t = x;
    x = y;
    y = t - (a / b) * y;
    return d;
}

int ce(int p, int q)
{
    return (int)((p + q - 1) / q);
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while(t--)
    {
        cin >> a >> b >> c;
        // gcd x0 y0
        // int gcd = exgcd(max(a, b), min(a, b));
        int gcd = exgcd(a, b);
        // cout << "   x == " << x << ", y == " << y << endl;
        if(c % gcd)  // 没有整数解
        {
            cout << -1 << endl;
            // cout << endl;
            continue;
        }
        // cout << "   gcd == " << gcd << endl;
        // x1 y1
        x *= (c / gcd);
        y *= (c / gcd);
        // cout << "   x == " << x << ", y == " << y << endl;
        // step
        int dx = b / gcd;
        int dy = (a / gcd);
        // min/maxr
        int l = ce((-x) / dx);
        int r = (int)(y / dy);
        if(l > r) // 没有正整数解
        {
            cout << x + l * dx << " " << y - r * dy << endl;
            // cout << endl;
            continue;
        }

        // 有正整数解
        int mxx = x + r * dx;
        int mxy = y - l * dy;
        int mnx = x + l * dx;
        int mny = y - r * dy;
        cout << (r - l + 1) << " " << mnx << " " << mny << " " << mxx << " " << mxy << endl;
        x = 0;
        y = 0;
        // cout << endl;
    }

    return 0;
}

样例没过

2024/10/1 20:38
加载中...