Cod sursa(job #2446675)

Utilizator miguelMihail Lavric miguel Data 10 august 2019 13:29:54
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.87 kb
/*
░░░░░░░░░░░░░░░░▄▄█▀▀██▄▄░░░░░░░
░░░░░░░░░░░░░▄█▀▀░░░░░░░▀█░░░░░░
░░░░░░░░░░░▄▀░░░░░░░░░░░░░█░░░░░
░░░░░░░░░▄█░░░░░░░░░░░░░░░█░░░░░
░░░░░░░██▀░░░░░░░▄▄▄░░▄░█▄█▄░░░░
░░░░░▄▀░░░░░░░░░░████░█▄██░▀▄░░░
░░░░█▀░░░░░░░░▄▄██▀░░█████░██░░░
░░░█▀░░░░░░░░░▀█░▀█▀█▀▀▄██▄█▀░░░
░░░██░░░░░░░░░░█░░█░█░░▀▀▄█▀░░░░
░░░░█░░░░░█░░░▀█░░░░▄░░░░░▄█░░░░
░░░░▀█░░░░███▄░█░░░░░░▄▄▄▄█▀█▄░░
░░░░░▀██░░█▄▀▀██░░░░░░░░▄▄█░░▀▄░
░░░░░░▀▀█▄░▀▄▄░▄░░░░░░░███▀░░▄██
░░░░░░░░░▀▀▀███▀█▄░░░░░█▀░▀░░░▀█
░░░░░░░░░░░░▄▀░░░▀█▄░░░░░▄▄░░▄█▀
░░░▄▄▄▀▀▀▀▀█▀░░░░░█▄▀▄▄▄▄▄▄█▀▀░░
░▄█░░░▄██▀░░░░░░░░░█▄░░░░░░░░░░░
█▀▀░▄█░░░░░░░░░░░░░░▀▀█▄░░░░░░░░
█░░░█░░░░░░░░░░░░░░░░░░█▄░░░░░░░
*/
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define x first
#define y second
#define pi pair <int, int>
#define vi vector <int>
//#define =1e9 =(int)1e9
const ll mod = 1000000007;
const ll nmax=1000003;
#define int ll
int t;

int gcd(int a, int b){
    if(a==0) return b;
    else return gcd(b%a, a);
}

pi gcde(int a, int b){
    if(a==0) return {0, 1};
    else{
        pi ans1=gcde(b%a, a);
        pi ans;
        ans.x=ans1.y-(b/a)*ans1.x;
        ans.y=ans1.x;
        return ans;
    }
}

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    ifstream cin("euclid3.in");
    ofstream cout("euclid3.out");
    cin>>t;
    while(t--){
        int a, b, xd, d;
        bool ctrl=0;
        cin>>a>>b>>xd;
        d=gcd(a, b);
        //dbg(d);
        if(xd%d==0) ctrl=1;
        xd/=d;
        pi ans=gcde(a, b);
        if(ctrl) cout<<ans.x*xd<<" "<<ans.y*xd<<"\n";
        else cout<<"0 0\n";
    }
}