Cod sursa(job #1295342)

Utilizator catalincraciunCraciun Catalin catalincraciun Data 19 decembrie 2014 12:00:20
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
// euclid3 - Algoritmul lui Euclid extins
//  Aplicatii - invers modular
#include <iostream>
#include <fstream>

using namespace std;

ifstream f("euclid3.in");
ofstream g("euclid3.out");

int t;

inline int gcd( int A, int B, int &X, int &Y )
{
    if (B == 0)
    {
        X = 1;
        Y = 0;
        return A;
    }
 
    int X0, Y0, D;
    D = gcd( B, A % B, X0, Y0 );
     
    X = Y0;
    Y = X0 - (A / B) * Y0;
    return D;
}

int cmmdc (int a, int b, int *x, int *y) {

	if (b == 0) {
		*x = 1;
		*y = 0;
		return a;
	} else {
		int x0, y0;
		int d = cmmdc(b, a%b, &x0, &y0);
		*x = y0;
		*y = x0 - (a / b) * y0;
		return d;
	}

	return -1;
}

void read() {

	f>>t;
	for (int i=1;i<=t;i++) {
		int a, b, c;
		f>>a>>b>>c;
		int solx, soly;
		int d = cmmdc(a, b, &solx, &soly);
		if (c % d != 0)
			g<<0<<' '<<0<<'\n';
		else {
			int fact = c/d;
			g<<solx*fact<<' '<<soly*fact<<'\n';
		}
	}
}

int main() {

	read();

	f.close(); g.close();
	return 0;
}