Cod sursa(job #2522805)

Utilizator nicu_ducalNicu Ducal nicu_ducal Data 13 ianuarie 2020 00:38:26
Problema Algoritmul lui Euclid extins Scor 70
Compilator py Status done
Runda Arhiva educationala Marime 0.7 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)