Cod sursa(job #3242602)

Utilizator DunareTanasescu Luca-Ioan Dunare Data 12 septembrie 2024 19:19:36
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f( "euclid3.in" );
ofstream g( "euclid3.out" );

void EuclidExtins( int a, int b, int &d, int &x, int &y ) ///Varianta recursiva
{
    if( b == 0 )
    {
        x = 1, y = 0, d = a;
    }
    else
    {
        int x0, y0;
        EuclidExtins( b, a % b, d, x0, y0 );
        x = y0;
        y = x0 - ( a / b ) * y0;
    }
}

int main()
{
    int n;
    f >> n;
    for( int i = 1; i <= n; i++ )
    {
        int a, b, d, x, y,c;
        f >> a >> b>>c;
        EuclidExtins( a, b, d, x, y );
        if(c%d!=0)
            g<<"0 0\n";
        else {
            int k=c/d;
            x*=k;
            y*=k;
            g<<x<<' '<<y<<'\n';
        }

        //g<<x<<' '<<y<<'\n';
    }
    //while( x < 0 )x += b;
    //g << x;
    return 0;
}

/**
 1) În scrierea a∙x + b∙y = d, x și y nu sunt neapărat unice.
    Pentru a verifica și obtine diferite valori, în funcția
    EuclidExtins, la cazul b == 0, putem atribui orice valoare lui y.
*/