Cod sursa(job #2737444)

Utilizator raducostacheRadu Costache raducostache Data 4 aprilie 2021 19:15:58
Problema Algoritmul lui Euclid extins Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <stdio.h>
#include <utility>

using namespace std;

int gcd(int, int, pair <int, int> &);

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

    int T;
    fscanf(f, "%d\n", &T);

    while (T--) {
        int x, y, t;
        fscanf(f, "%d %d %d\n", &x, &y, &t);
        pair <int, int> ans;
        int cmmdc = gcd(x, y, ans);
        if (t % cmmdc) {
            fprintf(g, "0 0\n");
            continue;
        }
        fprintf(g, "%d %d\n", ans.first * t / cmmdc, ans.second * t / cmmdc);
    }
    return 0;
}

int gcd(int a, int b, pair <int, int> & ans) {
    int r = a % b;
    pair <int, int> ares = {1, 0}, bres = {0, 1}, rres = {1, -(a / b)};
    while (r) {
        a = b;
        ares = bres;
        b = r;
        bres = rres;
        r = a % b;
        rres = {ares.first - (a / b) * bres.first, ares.second - (a / b) * bres.second};

    }
    ans = bres;
    return b;

}