Cod sursa(job #2676579)

Utilizator IoanMihaiIoan Mihai IoanMihai Data 24 noiembrie 2020 17:02:55
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.67 kb
#include <bits/stdc++.h>
using namespace std;
int a, b, c, x, y, t, d;
int euclid(int A,int B,int &X,int &Y)
{
    if (B == 0){
        X = 1;
        Y = 0;
        return A;
    } else{
        int x0, y0, ans;
        ans = euclid(B, A%B, x0, y0);
        X = y0;
        Y = x0 - A/B*y0;
        return ans;
    }
}
int main() {
    freopen("euclid3.in", "r", stdin);
    freopen("euclid3.out", "w", stdout);

    scanf("%d", &t);
    for (int i=1;i<=t;i++){
        scanf("%d%d%d", &a, &b, &c);
        d = euclid(a, b, x, y);
        if (c%d != 0){
            printf("%d %d\n", 0, 0);
        }else {
            printf("%d %d\n", x*(c/d), y*(c/d));
        }
    }
    return 0;
}