Cod sursa(job #2737451)

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

using namespace std;

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

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

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

    while (T--) {
        long long x, y, t;
        fscanf(f, "%d %d %d\n", &x, &y, &t);
        if (x == 0 && y == 0) {
            fprintf(g, "0 0\n");
            continue;
        }
        if (x == 0) {
            if (t % y)
                fprintf(g, "0 0\n");
            else
                fprintf(g, "%d %d\n", 0, t / y);
            continue;
        }
        else
            if (y == 0) {
                if (t % x)
                    fprintf(g, "0 0\n");
                else
                    fprintf(g, "%d %d\n", 0, t / x);
                continue;
            }
        pair <long, long> ans;
        long long 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;
}

long long gcd(long long a, long long b, pair <long, long> & ans) {
    long long r = a % b;
    pair <long, long> 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;

}