Cod sursa(job #2513198)

Utilizator butasebiButa Gabriel-Sebastian butasebi Data 22 decembrie 2019 15:31:27
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 ii, n, a, b, c, d, x, y;
int gcd(int a, int b, int & x, int & y)
{
    if(a == 0)
    {
        x = 0;
        y = 1;
        return b;
    }
    int x1, y1;
    int d = gcd(b % a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return d;
}
int main()
{
    ifstream f("euclid3.in");
    ofstream g("euclid3.out");
    f >> n;
    for(ii = 1; ii <= n; ii ++)
    {
        f >> a >> b >> d;
        c = gcd(a, b, x, y);
        if(d % c != 0)
        {
            g << "0 0" << "\n";
            continue;
        }
        g <<(d / c) * x << " " << (d / c) * y << "\n";
    }
    return 0;
}