Cod sursa(job #2691037)

Utilizator andrei_marciucMarciuc Andrei andrei_marciuc Data 26 decembrie 2020 19:43:02
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <stdio.h>

void calculez( long long a, long long b, long long *mul, long long *x, long long *y )
{
    if( b == 0 ) {
        *mul = a;
        *x = 1;
        *y = 0;
    } else {
        long long x0, y0;
        calculez( b, a % b, mul, &x0, &y0 );
        *x = y0;
        *y = x0 - ( a / b ) * y0;
    }
}

int main()
{
    int q;
    FILE *fin = fopen( "euclid3.in", "r" );
    FILE *fout = fopen( "euclid3.out", "w" );
    fscanf( fin, "%d", &q );
    while( q-- ) {
        long long a, b, c, x, y, mul;
        fscanf( fin, "%lld %lld %lld", &a, &b, &c );
        calculez( a, b, &mul, &x, &y );
        if( c % mul == 0 )
            fprintf( fout, "%lld %lld\n", x * ( c / mul ), y * ( c / mul ) );
        else fprintf( fout, "0 0\n" );
    }
    fclose( fin );
    fclose( fout );
    return 0;
}