80pts求助
查看原帖
80pts求助
366937
too_simple楼主2022/10/11 21:22
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

#define int long long

using namespace std;

int n;
int a, b, c;
int minx, miny, maxx, maxy;
int times, aa, bb, downx, lcm, gcd;

inline int read() {
    int x = 0;
    char c = getchar();
    while(c < '0' || c > '9') {
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = (x << 1) + (x << 3) + c - '0';
    }
    return x;
}

int getgcd(int a, int b, int &x, int &y) {
    if(b == 0) {
        x = 1, y = 0;
        return a;
    }
    int d = getgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}

signed main() {
    
//    freopen("test.in", "r", stdin);
//	freopen("test.out", "w", stdout);
    
    cin >> n;
    
    while(n -- ) {
        cin >> a >> b >> c;
        int x, y;
        gcd = getgcd(a, b, x, y);
        if(c % gcd) puts("-1");
        else {
            times = c / gcd;
            aa = a, bb = b;
            downx = b / gcd;
            x *= times, y *= times;
            lcm = a * b / gcd;
            a *= x, b *= y;
            minx = ((a % lcm) + lcm) % lcm;
            if(minx == 0) minx += lcm;
            maxy = c - minx;
            miny = ((b % lcm) + lcm) % lcm;
            if(miny == 0) miny += lcm;
            maxx = c - miny;
            if(maxx > 0 && maxy > 0) {
                printf("%lld %lld %lld %lld %lld\n", (maxx - minx) / aa / downx + 1, minx / aa, miny / bb, maxx / aa, maxy/ bb);
            }
            else {
                printf("%lld %lld\n", minx / aa, miny / bb);
            }
        }
    }
    
    return 0;
}
2022/10/11 21:22
加载中...