Cod sursa(job #657207)

Utilizator slycerdan dragomir slycer Data 5 ianuarie 2012 22:43:11
Problema Algoritmul lui Euclid extins Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
/* 
 * File:   AlgoritmulluiEuclidextins.cpp
 * Author: slycer
 *
 * Created on January 5, 2012, 10:10 PM
 */

#include <cstdlib>

#include <fstream>
#include <iostream>

using namespace std;

/*
 * 
 */
int ** dp; 
void init(){
    int k=32;
    dp = new int*[k]; 
    for ( int  i=0; i<32; i++){
        dp[i] = new int[3]; 
    }
}
int * euclid( int a, int b ){
    
    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");
    
    init();
    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;
}