Cod sursa(job #1326143)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 24 ianuarie 2015 19:13:20
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include<cstdio>

using namespace std;

FILE *fin = fopen( "euclid3.in", "r" ), *fout = fopen( "euclid3.out", "w" );

void eeuclid( int a, int b, int &x, int &y, int &d ) {
    if ( b == 0 ) {
        x = 1;
        y = 0;
        d = a;
        return ;
    }
    int xx, yy, q = a / b;
    eeuclid( b, a % b, xx, yy, d );
    x = yy;
    y = xx - yy * q;
}
int main() {
    int a, b, x, y, c, d, q;
    fscanf( fin, "%d", &q );
    while ( q -- ) {
        fscanf( fin, "%d%d%d", &a, &b, &c );
        eeuclid( a, b, x, y, d );
        if ( c % d == 0 ) {
            c /= d;
            fprintf( fout, "%d %d\n", x * c, y * c);
        } else {
            fprintf( fout, "0 0\n" );
        }
    }
    fclose( fin );
    fclose( fout );
    return 0;
}