Pagini recente » Cod sursa (job #759226) | Cod sursa (job #2553023) | Cod sursa (job #533758) | Istoria paginii runda/23dezile_3/clasament | Cod sursa (job #1455104)
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
ifstream fin ("euclid3.in") ;
ofstream fout ("euclid3.out") ;
int T , a , b ,c ;
int cmmdc ( int a , int b )
{
int rest = 1;
while ( rest != 0 )
{
rest = a % b ;
a = b ;
b = rest ;
}
return a ;
}
bool hassolutions ( int a , int b , int c )
{
if ( c % cmmdc (a,b) == 0 )
return 1 ;
return 0 ;
}
pair <int,int> ExtendedEuclidean ( int a ,int b , int c )
{
if ( hassolutions ( a , b , c ) == 0 )
return make_pair (0,0) ;
int x_0 = 1 , y_0 = 0 , x_1 = 0 , y_1 = 1 ;
int a_0 = a , b_0 = b ;
if ( a < 0 ) a_0 = (-1) * a_0 ;
if ( b < 0 ) b_0 = (-1) * b_0 ;
if ( a_0 < b_0 )
int aux = a_0 , a_0 = b_0 , b_0 = aux ;
int x_r , y_r ;
int q , r , gcd ;
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 <int,int> * rez = new pair <int,int > ;
while ( T >= 1 )
{
fin >> a >> b >> c ;
*rez=ExtendedEuclidean(a,b,c);
fout << rez->first << " " << rez->second << "\n" ;
-- T ;
}
delete rez ;
return 0;
}