Cod sursa(job #3302092)

Utilizator robigiirimias robert robigi Data 2 iulie 2025 23:53:31
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#include <cassert>

using namespace std;

int gcd(int a, int b, int &x, int &y)
{
    if (b == 0) 
    {
        x = 1;
        y = 0;
        return a;
    }
    int x0, y0;
    int d = gcd(b, a%b, x0, y0);

    x = y0;
    y = x0 - (a / b) * y0;
    return d;
}

int main()
{
    ifstream fin("euclid3.in");
    ofstream fout("euclid3.out");

    int n;
    fin >> n;

    for (int i=0; i<n; ++i)
    {
        int x, y, z;
        fin >> x >> y >> z;

        assert( -1000000000 <= x && x <= 1000000000 );
		assert( -1000000000 <= y && y <= 1000000000 );
		assert( -2000000000 <= z && z <= 2000000000 && z != 0 );

        int x0, y0;
        int d = gcd(x, y, x0, y0);

        if (z % d != 0) 
        {
            fout << "0 0" << endl;
        } 
        else 
        {
            x0 *= z / d;
            y0 *= z / d;

            // Output the solution
            fout << x0 << " " << y0 << endl;
        }

    }
    

    return 0;
}