Cod sursa(job #1114515)

Utilizator avram_florinavram florin constantin avram_florin Data 21 februarie 2014 18:30:34
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
//Sa se determine x,y numere intregi astfel incat ele sa respecte ecuatia:
//a*x+b*y=c , unde a,b,c sunt numere intregi
//Ideea: Se foloseste algoritmul lui Euclid extins
//Plecam de la cazul de baza cand b=0 si cmmdc=a si atunci a*1+b*0=a, deci initial x=1, y=0 cand b=0;
//Incercam apoi sa calculam x,y la pasul curent in functie de x0 si y0 calculate la pasul anterior
// b*x0 + (a%b)*y0 = d
// a*x + b*y = d
// 
// Notam c = [a/b] => a%b = a-c*b;
// Egaland ecuatiile obtinem x = y0 si y = x0 - c*y0

#include <iostream>
#include <fstream>
#include <cstdlib>

const char InFile[] = "euclid3.in";
const char OutFile[] = "euclid3.out";

int euclid_extins(int a, int b, int& x, int& y)
{
    if( b == 0 ){
        x = 1;
        y = 0;
        return a;
    }

    int x0, y0, d;
    d = euclid_extins(b, a%b, x0, y0);
    y = x0 - (a/b)*y0;
    x = y0;
    return d;
}

void readAndSolve(std::istream& in, std::ostream& out)
{
    int n, a, b, c, d, x, y;
    
    in >> n;
    for( int i=0 ; i<n ; i++ ){
        in >> a >> b >> c;
        d = euclid_extins(a, b, x, y);
        if( c % d ){
            out << 0 << ' ' << 0 << '\n';
        } else {
            x = x * (c/d);
            y = y * (c/d);
            out << x << ' ' << y << '\n';
        }
    }
}

int main(void)
{
    std::ifstream in(InFile);
    std::ofstream out(OutFile);

    readAndSolve(in, out);
    
    return 0;
}