Cod sursa(job #2214157)

Utilizator MoldooooooooMoldoveanu Stefan Moldoooooooo Data 18 iunie 2018 14:21:04
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 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);
        if(a==0){
            P=c/b;
            if(P*b==c) printf("%d %ld%c", 0, P, '\n');
            else printf("0 0%c", '\n');
            continue;
        }
        if(b==0){
            P=c/a;
            if(P*a==c) printf("%ld %d%c", P, 0, '\n');
            else printf("0 0%c", '\n');
            continue;
        }
        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;
}