扩展欧几里得

P5656 【模板】二元一次不定方程 (exgcd)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const ll N = 1e5 + 7;
const ll maxn = 1e5 + 7, maxm = 2e5 + 7;
inline ll read()
{
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57)
    {
        if (ch == '-')
            w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
inline void write(ll m)
{
    if (!m)
    {
        putchar('0');
        return;
    }
    char F[200];
    ll tmp = m > 0 ? m : -m;
    if (m < 0)
        putchar('-');
    int cnt = 0;
    while (tmp > 0)
    {
        F[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0)
        putchar(F[--cnt]);
}
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
ll exgcd(ll a, ll b, ll& x, ll& y)
{
    if(b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, x, y);
    ll z = x; x = y; y = z - y * (a / b);
    return d;
}
int main()
{
    ll t = read();
    while(t--){
        ll  a = read() , b = read(), c = read();
        ll x,y;
        ll d = exgcd(a,b,x,y);//求 ax + by = d 的特解x,y
        if(c % d){
            cout<<"-1"<<endl;
            continue;
        }
        ll m1 = b / d , m2 = a / d;
        x = c / d * x, y = c / d * y;//x,y是方程的特解
        ll minx,miny,maxx,maxy;
        /*if(x > 0 && x % m1 != 0)//cx/d+km1 是通解 
             minx = x % m1;
        else minx = x%m1 + m1;
        if(y > 0 && y % m2 != 0)//cy/d - km2是通解
            miny = y % m2;
        else miny = y%m2 +m2;*/
        minx = (x % m1 + m1) % m1;
        miny = (y % m2 + m2) % m2;
        if(!minx) minx += m1;
        if(!miny) miny += m2;
        maxy = (c - a * minx) / b;
        maxx = (c - b * miny) / a;//最大正整数解是当另一个最小时
        ll cnt = 0;
        if(maxx <= 0){
            cout<<minx<<" "<<miny<<" "<<endl;
        }
        else {
            cnt  =  (maxx - minx ) / m1 + 1;
            cout<<cnt<<" "<<minx<<" "<<miny<<" "<<maxx<<" "<<maxy<<endl;
        }
    }
}