Cod sursa(job #791153)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 23 septembrie 2012 10:50:02
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include<stdio.h>
#include<fstream>

using namespace std;

int t;
long long int a, b, c, d, x, y;

void euclid(long long int a, long long int b, long long int &d, long long int &x, long long int &y)
{
    if(!b)
        d = a, x = 1, y = 0;
    else
    {
        long long int x0, y0;

        euclid(b, a%b, d, x0, y0);

        x = y0;
        y = x0 - (a / b) * y0;
    }

}
int main()
{
    ifstream f("euclid3.in");

    f >> t;

    FILE *g = fopen("euclid3.out", "w");

    while(t)
    {
        f >> a >> b >> c;

        euclid(a, b, d, x, y);

        if(c%d)
            fprintf(g, "0 0\n");

        else
            fprintf(g, "%lld %lld\n", x*(c/d), y*(c/d));

        --t;
    }

    f.close();

    fclose(g);

    return 0;
}