Cod sursa(job #1114306)

Utilizator andreiagAndrei Galusca andreiag Data 21 februarie 2014 14:48:38
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <string>
#include <fstream>
#include <stdio.h>

using namespace std;

int x, y;

int extgcd(int a, int b) // a >= b && b >= 0;
{
    if (b == 0) { x = 1; y = 0; return a; }
    int q = a / b, r = a % b;
    int d = extgcd(b, r);
    int tmp = y;
    y = x - q * y;
    x = tmp;
    return d;
}

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

    int T, a, b, c, d, i, j, k, tmp;
    f >> T;
    for (;T; T--) {
        f >> a >> b >> c;
        // a, b > 0;
        i = (a < 0) ? -1 : 1;
        j = (b < 0) ? -1 : 1;
        k = (a < b) ? 1 : 0;
        a = (a < 0) ? -a : a;
        b = (b < 0) ? -b : b;
        if (a < b) { tmp = b; b = a; a = tmp; }
        d = extgcd(a, b);
        if (k) { tmp = x; x = y; y = tmp; }
        if (c % d != 0) g << 0 << ' ' << 0 << '\n';
        else
        {
            x *= i*c / d;
            y *= j*c / d;
            g << x << ' ' << y << '\n';
        }

    }

    return 0;
}