Cod sursa(job #2038977)

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

using namespace std;

long long div;

pair <long long, long long> euclidExtins(long long a, long long b)
{
    if(b == 0)
        {
            div = a;
            return {1, 0};
        }
    pair <long long, long long>  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);
    long long T, a, b, c;
    scanf("%lld", &T);
    for(int i=1; i<=T; ++i)
    {
        scanf("%lld%lld%lld", &a, &b, &c);
        pair <long long, long long>  p = euclidExtins(a, b);
        if(c%div == 0)
            printf("%lld %lld\n", p.first*(c/div), p.second*(c/div));
        else
            printf("0 0\n");
    }
    return 0;
}