Сложность алгоритма должна быть равна сложности алгоритма Евклида + константа.
#!/usr/bin/env python3
def nod(m, n):
return m if n == 0 else nod(n, m % n)
a = int(input("A = "))
b = int(input("B = "))
c = int(input("C = "))
assert c != 0
nodAB = nod(abs(a), abs(b))
if c % nodAB:
print("Impossible")
else:
a //= nodAB
b //= nodAB
c //= nodAB
for k in range(abs(a)):
if ( c - b * k ) % a == 0:
y = k
x = ( c - b * y ) // a
if x < 0:
x += b
y -= a
print("X =", x, "Y =", y)
break
else:
print("Shit happens!")
def gcd(a, b):
while a != 0 and b != 0:
if a < b:
b = b % a
else:
a = a % b
return a + b
def qwer(a, b):
x = 1
x1 = 0
y = 0
y1 = 1
while b != 0:
q = a // b
r = a % b
x2 = x - q * x1
y2 = y - q * y1
a, b = b, r
x, x1 = x1, x2
y, y1 = y1, y2
return str(a), str(x), str(y)
a, b, c = list(map(int, input().split()))
x, y = 0, 0
gcds = 0
if c % gcd(a, b) != 0:
print('Impossible')
else:
gcds, x, y = map(int, qwer(a, b))
x *= c // gcds
y *= c // gcds
q = x // (b // gcds)
x %= b // gcds
y += a // gcds * q
print(x, y)