Skip to content

Instantly share code, notes, and snippets.

@Askhab-rgb
Created May 10, 2025 10:31
Show Gist options
  • Save Askhab-rgb/60fdd96a20c4a56db274f7fe4908f84c to your computer and use it in GitHub Desktop.
Save Askhab-rgb/60fdd96a20c4a56db274f7fe4908f84c to your computer and use it in GitHub Desktop.
def extended_gcd(a, b):
if b == 0:
return (a, 1, 0)
else:
g, x1, y1 = extended_gcd(b, a % b)
x = y1
y = x1 - (a // b) * y1
return (g, x, y)
a = int(input())
b = int(input())
c = int(input())
d, x0, y0 = extended_gcd(a, b)
if c % d != 0:
print("Impossible")
else:
k = c // d
x_part = x0 * k
y_part = y0 * k
b_div_d = b // d
a_div_d = a // d
x_min = x_part % b_div_d
t = (x_min - x_part) // b_div_d
y_min = y_part - a_div_d * t
print(x_min, y_min)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment