Cod sursa(job #3139645)

Utilizator MilitaruMihai2022Millitaru Mihai MilitaruMihai2022 Data 30 iunie 2023 15:25:14
Problema Algoritmul lui Euclid extins Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f ( "euclid3.in" );
ofstream g ( "euclid3.out" );

void Euclid ( int a, int b, int &d ) ///recursiv
{
    if ( b == 0 )
        d = a;
    else
        Euclid ( b, a % b, d );
}

void EuclidExtins ( int a, int b, int &d, int &x, int &y )
{
    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 k;
    f >> k;
    while ( k-- )
    {
        int x, y, d, a, b, c;
        f >> a >> b >> c;
        EuclidExtins ( a, b, d, x, y );
        if ( c %  d  == 0 )
        {
            g << x*c / d << ' ' << y*c / d << '\n';
        }
        else
        {
            g << 0 << ' ' << 0 << '\n';
        }
    }
    return 0;
}