Cod sursa(job #2038944)

Utilizator B_RazvanBaboiu Razvan B_Razvan Data 14 octombrie 2017 10:10:48
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <iostream>
#include <cstdio>

using namespace std;

int div;

pair <long long, long long> euclidExtins(int a, int b)
{
    if(b == 0)
        {
            div = a;
            return {1, 0};
        }
    auto p = euclidExtins(b, a%b);
    return {p.second, p.first - (a/b)*p.second};
}

int main()
{
    freopen("euclid3.in", "r", stdin);
    freopen("euclid3.out", "w", stdout);
    int T, a, b, c;
    scanf("%d", &T);
    for(int i=1; i<=T; ++i)
    {
        scanf("%d%d", &a, &b, &c);
        auto p = euclidExtins(a, b);
        if(c%div == 0)
            printf("%lld %lld\n", p.first*div, p.second*div);
        else
            printf("0 0\n");
    }
    return 0;
}