题解

数论题目难得没边

#include <iostream>
using namespace std;
typedef long long ll;
ll mxx = -1e18, mxy = -1e18;
ll mnx = 1e18, mny = 1e18;
ll cnt;
ll exgcd(ll a, ll b, ll &x, ll &y){
    if(b == 0){
        x = 1;
        y = 0;
        cnt++;
        mxx = max(mxx, x);
        mxy = max(mxy, y);
        return a;
    }
    ll x1, y1;
    ll g = exgcd(b, a%b, x1, y1);
    mxx = max(mxx, x);
    mxy = max(mxy, y);
    mnx = min(mnx, x1);
    mny = min(mny, y1);
    x = y1;
    y = x1 - a/b*y1;
    cnt++;
    return g;
}
ll ceil_div(ll p, ll q){
    if(p == 0) return 0;
    if(p > 0) return (p + q - 1) / q;
    else return p / q;
}
ll floor_div(ll p, ll q){
    if(p % q == 0) return p / q;
    if(p < 0) return p / q - 1;
    else return p / q;
}
void solve(){
    ll a, b, c;
    cin >> a >> b >> c;
    ll x0, y0;
    ll g = exgcd(a, b, x0, y0);
    if(c % g != 0) { // 无解
        cout << -1 << endl;
        return ;
    }
    ll x1 = x0 * c / g;
    ll y1 = y0 * c / g;
    ll dx = b / g;
    ll dy = a / g;
    ll t_l = ceil_div(1 - x1, dx);
    ll t_r = floor_div(y1 - 1, dy);
    if(t_l <= t_r){// 有正整数解
        ll cnt = t_r - t_l + 1;
        ll x_min = x1 + dx * t_l;
        ll x_max = x1 + dx * t_r;
        ll y_min = y1 - dy * t_r;
        ll y_max = y1 - dy * t_l;
        cout << cnt << " " << x_min << " " << y_min << " " << x_max << " " << y_max << endl;
    }
    else{// 无正整数解
        ll xmin = (x1 % dx + dx) % dx;
        if(xmin == 0) xmin = dx;
        ll ymin = (y1 % dy + dy) % dy;
        if(ymin == 0) ymin = dy;
        cout << xmin << " " << ymin << endl;
    }
}
int main(){
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}