Pagini recente » Cod sursa (job #2935275) | Cod sursa (job #689453) | Cod sursa (job #1581023) | Cod sursa (job #3126701) | Cod sursa (job #2522808)
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)