Pagini recente » Cod sursa (job #2203833) | Cod sursa (job #1318370) | Cod sursa (job #2947317) | Cod sursa (job #1463159) | Cod sursa (job #1455137)
#include <iostream>
#include <fstream>
#include <cmath>
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;
}