Cod sursa(job #2214049)

Utilizator MoldooooooooMoldoveanu Stefan Moldoooooooo Data 18 iunie 2018 12:37:56
Problema Algoritmul lui Euclid extins Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <cstdio>
#include <string.h>
#define max(a, b) (a>b?a:b)
#define min(a, b) (a<b?a:b)
using namespace std;
int long N, i, a, b, D, x, y, List[101], I, R, x0, y0, vf, P, c;
bool Reverse;
int main()
{
    FILE *fin, *fout;
    fin=freopen("euclid3.in", "r", stdin);
    fout=freopen("euclid3.out", "w", stdout);
    scanf("%ld", &N);
    for(i=1; i<=N; i++){
        Reverse=0; vf=0;
        scanf("%ld%ld%ld", &a, &b, &c);
        D=max(a, b); I=min(a, b); R=D%I; if(D==b && D!=a) Reverse=1;
        while(R){
            List[++vf]=D/I;
            D=I;
            I=R;
            R=D%I;
        }
        List[++vf]=D/I;
        x0=1; y0=0;
        P=c/I;
        if(P*I!=c){printf("%d %d%c", 0, 0, '\n'); continue;}
        for(int j=vf; j>=1; j--){
            x=y0;
            y=x0-List[j]*y0;
            y0=y; x0=x;
        }
        x*=P; y*=P;
        if(Reverse)printf("%ld %ld%c", y, x, '\n');
        else printf("%ld %ld%c", x, y, '\n');
    }
    return 0;
}