Cod sursa(job #2145159)

Utilizator SolcanMihaiSolcan Mihai Andrei SolcanMihai Data 27 februarie 2018 10:12:42
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <cstdio>
#include <vector>

using namespace std;

int dd = 0;

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

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

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

    for(int i = 0; i < t; i++){
        int x, y, d;
        scanf("%d %d %d", &x, &y, &d);

        pair<int, int> z = euclidExtins(x, y);

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

    return 0;
}