Cod sursa(job #2353717)

Utilizator DysKodeTurturica Razvan DysKode Data 24 februarie 2019 15:32:35
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin(".in");

#define f first
#define s second

int i,j,n,m,k,o,p,grad[2010],use[2010],cost[2010],a[2010],b[2010];
char aa[1010][1010];
vector< int > G[2010],egal[2010];
queue< int > Q;




///euclid( 4 , 6 )
///euclid( 6 , 4 )
///euclid( 4 , 2 )
///euclid( 2 , 0 ) a=2 b=0




void euclid( int a, int b , int &d , int &x, int &y )
{
    if( b == 0 )
    {
        d = a;
        x = 1;
        y = 0;
        ///  a = cmmdc(a,b) , b = 0
        /// a*x + b*y = d
        /// x0 = 1   y0 = 0
        /// a*x0 + b*y0 = d
        /// b*x0 + (a%b)*y0 = d
        /// b*x0 + ( a - b*c )*y0 = d ( a,b,c sunt variabile
                                    ///din recursivitatea anterioara )
        return;
    }

    int x0, y0;
    euclid( b , a % b , d , x0 , y0 );

    /// a - b * c , c = a/b
    /// a*x + b*y = d
    /// b*x0 + ( a - b*c )*y0 = d
    /// a*x + b*y = b*x0 + (a - b*c)*y0
    /// a( x - y0 ) = b( x0 -c*y0 - y )
    /// x = y0;
    /// y = x0 - c*y0
    x = y0;
    y = x0 - ( a/b )*y0;
}

int main()
{
    ifstream fin("euclid3.in");
    ofstream fout("euclid3.out");
    int n;
    int a,b,x,y,d,c;
    fin >> n;
    for( int i = 1 ; i <= n ; i++ )
    {
        fin >> a >> b >> c;
        euclid( a , b , d , x , y );
        if( c % d == 0 )
        {
            fout << x * ( c / d ) << ' ' << y * ( c / d ) << '\n';
        }
        else
        {
            fout << 0 << ' ' << 0 << '\n';
        }
    }


return 0;
}