Cod sursa(job #3255539)

Utilizator andiRTanasescu Andrei-Rares andiR Data 10 noiembrie 2024 23:05:01
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
// Author: Tanasescu Andrei-Rares
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <deque>
#include <iomanip>
#include <vector>
#include <cassert>

#pragma GCC optimize("O3")

#define fi first
#define se second
#define pb push_back
#define pf push_front

using namespace std;

ifstream fin ("euclid3.in");
ofstream fout ("euclid3.out");

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll Nmax=1e6+5, inf=1e9+5;

int t;
ll a, b, c;

inline ll gcd_ext(ll a, ll b, ll &x, ll &y){
    ll xa=1, ya=0;
    ll xb=0, yb=1;
    ll d, r;
    while (b!=0){
        d=a/b;
        r=a%b;

        xa=xa-xb*d;
        ya=ya-yb*d;

        swap(xa, xb);
        swap(ya, yb);

        a=b;
        b=r;
    }
    x=xa;
    y=ya;
    return a;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    fin>>t;
    while (t--){
        fin>>a>>b>>c;
        ll x, y, gcd;
        gcd=gcd_ext(a, b, x, y);

        if (c%gcd!=0)
            fout<<"0 0\n";
        else{
            c/=gcd;
            x*=c;
            y*=c;

            fout<<x<<' '<<y<<'\n';
        }
    }

    return 0;
}