Cod sursa(job #2510500)

Utilizator XsoundCristian-Ioan Roman Xsound Data 16 decembrie 2019 20:18:25
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <bits/stdc++.h>

using namespace std;

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

int euclid ( int a, int b, int *X, int *Y )
{
    if ( b == 0 )
    {
        *X = 1;
        *Y = 0;

        return a;
    }

    else
    {
        int X0, Y0, d;

        d = euclid ( b , a%b , &X0, &Y0 );

        *X = Y0;
        *Y = X0 - (a/b) * Y0;

        return d;
    }
}

void read ( );

int main ( )
{
    read ( );
}

void read ( )
{
    long long int a, b, c, t;
    int d, X, Y;

    fin >> t;

    while ( t-- )
    {
        fin >> a >> b >> c;

        d = euclid ( a, b, &X, &Y );

        if ( c % d == 0 )
            fout << X*(c/d) << ' ' << Y*(c/d) << '\n';

        else
            fout << 0 << ' ' << 0 << '\n';
    }
}