Pagini recente » Cod sursa (job #1512281) | Cod sursa (job #186117) | Cod sursa (job #241334) | Cod sursa (job #2109878) | Cod sursa (job #657203)
Cod sursa(job #657203)
/*
* File: AlgoritmulluiEuclidextins.cpp
* Author: slycer
*
* Created on January 5, 2012, 10:10 PM
*/
#include <cstdlib>
#include <fstream>
#include <iostream>
using namespace std;
/*
*
*/
int * euclid( int a, int b ){
int ** dp = new int*[100];
for ( int i=0; i<100; i++){
dp[i] = new int[3];
}
dp[0][0] = a, dp[0][1] = 1, dp[0][2] = 0;
dp[1][0] = b, dp[1][1] = 0, dp[1][2] = 1;
int i=1;
while ( true ){
int cat = dp[i-1][0]/dp[i][0];
int rest = dp[i-1][0]%dp[i][0];
if ( rest == 0 ){
break;
}
i++;
dp[i][0] = rest;
dp[i][1] = dp[i-2][1] - cat * dp[i-1][1];
dp[i][2] = dp[i-2][2] - cat * dp[i-1][2];
cout << dp[i][0] << " " << dp[i][1] << " " << dp[i][2] << " " <<endl;
}
return dp[i];
}
int main(int argc, char** argv) {
ifstream input("euclid3.in");
ofstream output("euclid3.out");
int n;
input >> n;
for ( int i=0; i<n; i++ ){
int a,b,c;
input >> a >> b >> c;
int * r = euclid( a, b );
if ( c % r[0] == 0 ){
int cat = c/r[0];
r[1] = r[1] * cat;
r[2] = r[2] * cat;
output << r[1] << " " << r[2] << "\n";
} else{
output << "0 0" << "\n";
}
}
return 0;
}