Cod sursa(job #2053928)

Utilizator SolcanMihaiSolcan Mihai Andrei SolcanMihai Data 1 noiembrie 2017 15:37:24
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <iostream>

using namespace std;

int dx;

pair<int, int> euclidExtins(int a, int b){
    if(b != 0){
        auto x = euclidExtins(b, a % b);
        return {x.second, x.first - (a / b) * x.second};
    }
    else{
        dx = a;
        return {1, 0};
    }
};

pair<int, int> solve(int a, int b, int d){
    auto x = euclidExtins(a, b);

    if(d % dx != 0){
        return {0, 0};
    }
    else{
        return {x.first * (d / dx), x.second * (d / dx)};
    }
}

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

    int n;
    scanf("%d", &n);

    for(int i = 0; i < n; i++){
        int a, b, d;
        scanf("%d %d %d", &a, &b, &d);

        auto x = solve(a, b, d);
        printf("%d %d\n", x.first, x.second);
    }

    return 0;
}