#! /usr/bin/python
def gcd(a,b):
"""Returns the gcd of its inputs times the sign of b if b is nonzero,
and times the sign of a if b is 0.
"""
while b != 0:
a,b = b, a % b
return a
def xgcd(a,b):
"""Extended GCD:
Returns (gcd, x, y) where gcd is the greatest common divisor of a and b
with the sign of b if b is nonzero, and with the sign of a if b is 0.
The numbers x,y are such that gcd = ax+by."""
prevx, x = 1, 0; prevy, y = 0, 1
while b:
q, r = divmod(a,b)
x, prevx = prevx - q*x, x
y, prevy = prevy - q*y, y
a, b = b, r
return a, prevx, prevy
# EXPLANATION:
# Mathematical analysis reveals that at each stage in the calculation
# the current remainder can be expressed in the form ax + by for some
# integers x, y. Moreover, the x-sequence and y-sequence are
# generated by the recursion (where q is the integer quotient of the
# current division):
#
# new x = prev x - q * x; new y = prev y - q * y
#
# and where the initial values are x = 0, prev x = 1, y = 1, prev y = 0.
# Moreover, upon termination the x and y sequences have gone one step
# too far, (as has the remainder), so return the previous x, y values.
def mgcd(a,b):
"""Returns (gcd, x, y, s, t) where
gcd is the greatest common divisor of a and b, with the sign of b
if b is nonzero, and with the sign of a if b is 0;
the numbers x,y, s, t are such that
gcd = xa+yb
0 = sa+tb
and abs(xt-ys) = 1
Otherwise put: the determinant of matrix (hence m in name)
x y
s t
has magnitude 1, and multiplied by column vector
a
b
is column vector
gcd
0
"""
prevx, x = 1, 0; prevy, y = 0, 1
while b:
q, r = divmod(a, b)
x, prevx = prevx - q*x, x
y, prevy = prevy - q*y, y
a, b = b, r
return a, prevx, prevy, x, y
## Change from xgcd:
## The coefficients for next iteration of xgcd that give 0 there,
## and are excluded on purpose, are just included here as the last two
## returned values, so only the end of the last line is differentfrom xgcd.