Cod sursa(job #1892586)

Utilizator DanyBvGeorge-Daniel Gagiu DanyBv Data 25 februarie 2017 09:57:02
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <iostream>
#include <cstdio>

using namespace std;

long long k, l, d;
void euclid(long long a, long long b)
{
    if(b)
    {
        euclid(b, a % b);
        long long kv = k, lv = l;
        k = lv;
        l = kv - lv * (a / b);
        return;
    }
    d = a;
    k = 1;
    l = 0;
}

int main()
{
    int a, b, c, n;
    freopen("euclid3.in" , "r", stdin );
    freopen("euclid3.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        k = 1, l = 0;
        scanf("%d %d %d", &a, &b, &c);
        euclid(a, b);
        if(c % d)
        {
            printf("0 0\n");
            continue;
        }
        printf("%lld %lld\n", k * (c / d), l * (c / d));
    }
    return 0;
}