Cod sursa(job #1455214)

Utilizator petru.cehanCehan Petru petru.cehan Data 27 iunie 2015 14:25:47
Problema Floyd-Warshall/Roy-Floyd Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.13 kb
#include <iostream>
#include <fstream>

using namespace std;

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

long long  T , a , b ,c ;

long long cmmdc ( long long a , long long b )
{
    long long rest = 1;
    if ( a == 0 )
          return b ;
    if ( b == 0 )
          return a ;
    while ( rest != 0 )
    {
        rest = a % b ;
        a = b ;
        b = rest ;
    }
 return a ;
}

bool hassolutions ( long long a , long long b , long long c )
{
    if ( c % cmmdc (a,b) == 0 )
             return 1 ;
    return 0 ;
}

pair <long long,long long> ExtendedEuclidean ( long long a ,long long b , long long c )
{
    if ( hassolutions ( a , b , c ) == 0 )
          return make_pair (0,0) ;

    long long x_0 = 1 , y_0 = 0 , x_1 = 0 , y_1 = 1 ;
    long long a_0 = a , b_0 = b ;

    if ( a < 0 ) a_0 = (-1) * a_0 ;
    if ( b < 0 ) b_0 = (-1) * b_0 ;

    if ( c < 0 ) c = (-1) * c , a = (-1) * a , b = (-1) * b ;

    if ( a_0 < b_0 )
          long long aux = a_0 , a_0 = b_0 , b_0 = aux ;

    long long x_r , y_r ;
    long long q , r ;

    while ( b_0 != 0 )
    {
        q = a_0 / b_0 ;
        r = a_0 % b_0;
        a_0 = b_0 ;
        b_0 = r ;
        x_r = x_0 - q * x_1 ;
        y_r = y_0 - q * y_1 ;
        x_0 = x_1 ;
        y_0 = y_1 ;
        x_1 = x_r ;
        y_1 = y_r ;
    }
   // gcd = a_0 ;

   x_r = x_0 * c / cmmdc(a,b) ;
   y_r = y_0 * c / cmmdc(a,b) ;

   if ( a * x_r + b * y_r == c )
           return make_pair ( x_r, y_r ) ;
   if ( a * -(1) * x_r + b * y_r == c )
           return make_pair ( (-1) * x_r, y_r ) ;
   if ( a * x_r + b * (-1)* y_r == c )
           return make_pair ( x_r, (-1) * y_r ) ;
   if ( a * -(1) * x_r + b *(-1)* y_r == c )
           return make_pair ( (-1) * x_r, (-1) * y_r ) ;

}

int main()
{
    fin >> T ;
    pair <long long,long long> * rez = new pair <long long,long long > ;

    while ( T >= 1 )
    {
        fin >> a >> b >> c ;
        *rez=ExtendedEuclidean(a,b,c);
        fout << rez->first << " " << rez->second << "\n" ;
        -- T ;
    }

    delete rez  ;

    return 0;
}