Cod sursa(job #2038943)

Utilizator SolcanMihaiSolcan Mihai Andrei SolcanMihai Data 14 octombrie 2017 10:10:19
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <cstdio>
#include <utility>

using namespace std;

long long a, b, c;
long long d;

void citire(){
    scanf("%lld %lld %lld", &a, &b, &c);
}

pair <long long, long long> cmmdc(long long a, long long b){
    if(b == 0){
        d = a;
        return {1, 0};
    }
    else{
        auto p = cmmdc(b, a % b);

        return {p.second, p.first - (a / b) * p.second};
    }
};

void solve(){
    auto p = cmmdc(a, b);

    if(c % d != 0){
        printf("0 0\n");
    }
    else{
        printf("%lld %lld\n", p.first * (c / d), p.second * (c / d));
    }
}

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

    long long t;
    scanf("%lld", &t);

    for(long long k = 0; k < t; k++){
        citire();
        solve();
    }

    return 0;
}