Cod sursa(job #1116406)

Utilizator BonCipBonciocat Ciprian Mircea BonCip Data 22 februarie 2014 15:37:16
Problema Algoritmul lui Euclid extins Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.89 kb
#include <stdio.h>

typedef struct {
    int m, n;
} pair;

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

    int T;
    fscanf( fin, "%d", &T );

    int i;
    for( i = 1; i <= T; i ++ ) {
        int a, b, c;
        fscanf( fin, "%d%d%d", &a, &b, &c );

        pair r0, r1;
        r0.m = 1; r0.n = 0;
        r1.m = 0; r1.n = 1;
        while( a * r1.m + b * r1.n ) {
            pair r2;
            int q = ( r0.m * a + r0.n * b ) / ( r1.m * a + r1.n * b );
            r2.m = r0.m - r1.m * q;
            r2.n = r0.n - r1.n * q;
            r0 = r1;
            r1 = r2;
        }
        int d = r0.m * a + r0.n * b;
        if( c % d == 0 ) {
            fprintf( fout, "%d %d\n", r0.m * ( c / d ), r0.n * ( c / d ) );
        } else {
            fprintf( fout, "0 0\n" );
        }
    }

    fclose( fin );
    fclose( fout );
}