Cod sursa(job #2566217)

Utilizator stefan_creastaStefan Creasta stefan_creasta Data 2 martie 2020 19:45:08
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <cstdio>
using namespace std;
int cmmdc(int a, int b) {
    while(b) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}
struct Pas {
    int a, b;
};
Pas v[100000];

int main() {
    int T;
    freopen("euclid3.in", "r", stdin);
    freopen("euclid3.out", "w", stdout);
    scanf("%d", &T);
    while(T > 0) {
        T--;
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        int d = cmmdc(a, b);
        if(c % d != 0) {
            printf("0 0\n");
        }
        else {
            int top = 1;
            v[1] = {a, b};
            while(v[top].b != 0) {
                top++;
                v[top].a = v[top - 1].b;
                v[top].b = v[top - 1].a % v[top - 1].b;
            }
            int x = 1, y = 0;
            top--;
            while(top > 0) {
                int nx = y;
                int ny = x - y * (v[top].a / v[top].b);
                x = nx;
                y = ny;
                top--;
            }
            x *= (c / d);
            y *= (c / d);
            printf("%d %d\n", x, y);
        }
    }
    return 0;
}