Cod sursa(job #2964531)

Utilizator Alex_DumitrascuAlex Dumitrascu Alex_Dumitrascu Data 13 ianuarie 2023 09:58:45
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <iostream>
#include <cstdio>
using namespace std;
FILE *fin=fopen("euclid3.in", "r");
FILE *fout=fopen("euclid3.out", "w");
int extended_euclid (int a, int b, int &x, int &y)
{
    if (b==0) {
        x=1;
        y=0;
        return a;
    }
    int x0, y0;
    int gcd=extended_euclid(b, a%b, x0, y0);
    x=y0;
    y=x0-(a/b)*y0;
    return gcd;
}
int main()
{
    int n;
    fscanf(fin, "%d", &n);
    for (int i=0; i<n; i++) {
        int a, b, c;
        fscanf(fin, "%d%d%d", &a, &b, &c);
        int t1, t2;
        int gcd=extended_euclid(a, b, t1, t2);
        if (c%gcd) {
            fprintf(fout, "0 0\n");
        }
        else {
            fprintf(fout, "%d %d\n", t1*(c/gcd), t2*(c/gcd));
        }
        cout<<endl;
    }
    return 0;
}