Cod sursa(job #2522808)

Utilizator nicu_ducalNicu Ducal nicu_ducal Data 13 ianuarie 2020 00:44:00
Problema Algoritmul lui Euclid extins Scor 70
Compilator py Status done
Runda Arhiva educationala Marime 0.68 kb
def extended_gcd(a, b):
    s = 0;
    old_s = 1
    t = 1;
    old_t = 0
    r = b;
    old_r = a

    while r != 0:
        quotient = old_r // r
        (old_r, r) = (r, old_r - quotient * r)
        (old_s, s) = (s, old_s - quotient * s)
        (old_t, t) = (t, old_t - quotient * t)

    return old_r, old_s, old_t


with open('euclid3.in') as f:
    with open('euclid3.out', 'w') as g:
        t = int(f.readline())
        for line in f:
            a, b, c = map(int, line.split())
            d, x, y = extended_gcd(a, b)
            if c % d != 0:
                print(0, 0, file=g)
            else:
                print(x * (c // d), y * (c // d), file=g)