Cod sursa(job #3299667)

Utilizator Tuduce_RobertTuduce Robert Florin Tuduce_Robert Data 9 iunie 2025 03:46:13
Problema Algoritmul lui Euclid extins Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <stdio.h>

long long euclid_extins(long long a, long long b, long long *x, long long *y) {
    if (b == 0) {
        *x = 1;
        *y = 0;
        return a;
    }
    long long x1, y1;
    long long d = euclid_extins(b, a % b, &x1, &y1);
    *x = y1;
    *y = x1 - (a / b) * y1;
    return d;
}

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

    fscanf(fin,"%lld", &T);

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

        long long x0, y0;
        long long d = euclid_extins(a, b, &x0, &y0);

        if (c % d != 0) {
            fprintf(fout,"0 0\n");
        } else {
            long long coef = c / d;
            x0 *= coef;
            y0 *= coef;
            fprintf(fout,"%lld %lld\n", x0, y0);
        }
    }

    return 0;
}