Cod sursa(job #2017313)

Utilizator Alex18maiAlex Enache Alex18mai Data 31 august 2017 20:09:09
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <bits/stdc++.h>

using namespace std;

void euclid (int a , int b , int &d , int &x, int &y){
    if (b == 0){
        d = a;
        x = 1;
        y = 0;
    }
    else{
        int x0 ,y0;
        euclid (b , a%b , d , x0, y0);
        x = y0;
        y = x0 - (a / b) * y0;
    }
}

int main() {
    freopen ("euclid3.in" , "r" , stdin);
    freopen ("euclid3.out" , "w" , stdout);

    int t;
    cin>>t;
    while(t--){
        int a , b , d;
        cin>>a>>b>>d;
        int x , y , sol;
        euclid (a , b , sol , x , y);
        if (d % sol == 0){
            cout<<(d/sol)*x<<" "<<(d/sol)*y<<'\n';
        }
        else{
            cout<<0<<" "<<0<<'\n';
        }
    }
    return 0;
}