Cod sursa(job #3298383)

Utilizator CosminM12Murariu Rusalin - Cosmin CosminM12 Data 29 mai 2025 10:15:12
Problema Algoritmul lui Euclid extins Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <stdio.h>

long long extgcd(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 gcd = extgcd(b, a%b, &x1, &y1);

    *x = y1;
    *y = x1 - (a / b) * y1;

    return gcd;
}


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

    int t;
    fscanf(input, "%d", &t);

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

        long long x, y;
        long long gcd = extgcd(a, b, &x, &y);

        if(c % gcd != 0) {
            fprintf(output, "0 0\n");
        }
        else {
            x *= (c / gcd);
            y *= (c / gcd);

            fprintf(output, "%lld %lld\n", x, y);
        }
    }

    fclose(input);
    fclose(output);
    return 0;
}