Cod sursa(job #2373105)

Utilizator cristina-criCristina cristina-cri Data 7 martie 2019 12:16:54
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.69 kb
#include <cstdio>
#include <algorithm>

using namespace std;

int t, a, b, c, d;

pair <int, int> euclid_extins(int x, int y)
{
    if(y == 0)
    {
        d=x;
        return {1, 0};
    }
    auto p=euclid_extins(y, x%y);
    return {p.second, p.first-(x/y)*p.second};
}

int main()
{

    freopen("euclid3.in", "r", stdin);
    freopen("euclid3.out", "w", stdout);

    scanf("%d", &t);

    for(int i=1; i<=t; i++)
    {
        scanf("%d %d %d", &a, &b, &c);
        d=0;
        auto p=euclid_extins(a, b);
        if(c%d == 0)
            printf("%d %d\n", p.first*(c/d), p.second*(c/d));

        else
            printf("0 0\n");
    }

    return 0;
}