Cod sursa(job #3234297)

Utilizator catalinaionela77Catalina Ionela Florescu catalinaionela77 Data 8 iunie 2024 17:43:21
Problema Algoritmul lui Euclid extins Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 0.95 kb

#include <stdio.h>
#include <stdlib.h>


long long euclid(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(b, a % b, &x1, &y1);
    *x = y1;
    *y = x1 - (a / b) * y1;
    return d;
}

int main() {
    FILE *f1=fopen("euclid3.in", "r"),*f2=fopen("euclid3.out", "w");
    if(!f1||!f2)
    {
        perror(NULL);
        return 1;
    }

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

    while (t) {
        long long a, b, c;
        fscanf(f1, "%lld %lld %lld", &a, &b, &c);

        long long x, y;
        long long d =euclid(a, b, &x, &y);

        if (c % d != 0) {
            fprintf(f2, "0 0\n");
        } else {
            long long factor = c / d;
            fprintf(f2, "%lld %lld\n", x * factor, y * factor);
        }
        t--;
    }

    fclose(f1);
    fclose(f2);
    return 0;
}