Problem:
Extended Euclid Algorithm   Given positive integers a and b , find the integer solution ( x , y ) to ax + by = gcd(a, b) , where gcd(a, b) is the greatest common divisor of a and b .  Input   a  b   Two positive integers a and b are given separated by a space in a line.  Output  Print two integers x and y separated by a space. If there are several pairs of such x and y , print that pair for which |x| + |y| is the minimal (primarily) and x ≤ y (secondarily).  Constraints   1 ≤ a , b ≤ 10 9   Sample Input 1  4 12  Sample Output 1  1 0   Sample Input 2  3 8  Sample Output 2  3 -1

Solution (Python):



def vector_minus(v1, v2):
    return [elm1 - elm2 for elm1, elm2 in zip(v1, v2)]


def scalar_multi(scalar, vector):
    return [scalar*elm for elm in vector]


def gcd(n1, n2):
    if n1 < n2:
        n1, n2 = n2, n1

    if n1 == n2 or n2 == 0:
        return n1
    n1, n2 = n2, (n1 % n2)
    return gcd(n1, n2)


def solve_int(number1, number2):
    """
    answer1 = 1
    while True:
        if (1+number1*answer1) % number2 == 0:
            return -answer1, (1+number1*answer1)//number2
        answer1 += 1
    """
    if number1 < number2:
        if number1 == 1:
            return 1, 0
        reverse_flag = 1
        n1, n2 = number2, number1
    else:
        if number2 == 1:
            return 0, 1
        reverse_flag = 0
        n1, n2 = number1, number2

    quotient1 = []
    coeff1 = [1, 0]
    quotient2 = []
    coeff2 = [0, 1]

    while True:
        quotient1.append(n1//n2)
        coeff1 = vector_minus(coeff1, scalar_multi(n1//n2, coeff2))
        if n1 % n2 == 1:
            if reverse_flag:
                return coeff1[1], coeff1[0]
            else:
                return coeff1[0], coeff1[1]

        r_memo = n1 % n2
        quotient2.append(n2//r_memo)
        coeff2 = vector_minus(coeff2, scalar_multi(n2//r_memo, coeff1))
        if n2 % r_memo == 1:
            if reverse_flag:
                return coeff2[1], coeff2[0]
            else:
                return coeff2[0], coeff2[1]

        n1, n2 = n1 % n2, n2 % r_memo


def modify_solution(x_sp_s, y_sp_s, n1, n2):
    x_memo, y_memo = x_sp_s, y_sp_s
    if abs(x_sp_s + n2) + abs(y_sp_s - n1) < (abs(x_memo) + abs(y_memo)):
        m = y_sp_s//n1
        if m == 0:
            return x_sp_s+n2, y_sp_s-n1
        return modify_solution(x_sp_s + m*n2, y_sp_s - m*n1, n1, n2)
    if abs(x_sp_s + n2) + abs(y_sp_s - n1) == (abs(x_memo) + abs(y_memo)):
        pass
    return x_memo, y_memo


if __name__ == '__main__':
    a, b = map(int, input().split())
    right_side = gcd(a, b)
    if right_side > 1:
        a //= right_side
        b //= right_side

    x_sp, y_sp = solve_int(a, b)
    if x_sp > y_sp:
        m2 = x_sp//b
        x_sp -= (m2+1)*b
        y_sp += (m2+1)*a
    x_sp, y_sp = modify_solution(x_sp, y_sp, a, b)
    print(x_sp, y_sp)

Solution (Python):
def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a % b)

def extgcd(a,b):
    if b == 0:
        x = 1
        y = 0
        return (x,y)
    r = a % b
    (y,x) = extgcd(b,r)
    y -= a//b * x
    return (x,y)

a,b = map(int,input().split())
x,y = extgcd(a,b)
print(x,y)

Solution (Python):
def ext_gcd(a, b):
    if b == 0:
        return 1, 0
    q, t = divmod(a, b)
    x, y = ext_gcd(b, t)
    return y, (x - q * y)


def main():
   a, b = map(int, input().split())
   print(*ext_gcd(a,b))
   return


main()

Solution (Python):
def extended_euclid(a, b):
    x1, y1, m = 1, 0, a
    x2, y2, n = 0, 1, b
    while m % n != 0:
        q, r = divmod(m, n)
        x1, y1, m, x2, y2, n = x2, y2, n, x1 - q * x2, y1 - q * y2, r
    return (x2, y2, n)

a, b = map(int, input().split())
x, y, _ = extended_euclid(a, b)
print(x, y)

Solution (Python):
import sys
import itertools

def extend_gcd(a, b):
    if b == 0:
        return (1, 0, a)
    else:
        (a1, b1, g) = extend_gcd(b, a % b)
        return (b1, a1 - (a // b) * b1, g)
    
    
if __name__ == '__main__':
    line = sys.stdin.readline()
    a,b = line.split()
    a,b = int(a), int(b)
    
    (x, y, g) = extend_gcd(a, b)
    
    
    sys.stdout.write(str(x) + ' '  + str(y) +  '\n')

Solution (Python):
from sys import stdin
readline = stdin.readline

r0, r1 = map(int, readline().split())
a0, a1 = 1, 0
b0, b1 = 0, 1
while 0 < r1:
    q1 = r0 // r1
    a0, a1 = a1, a0 - q1 * a1
    b0, b1 = b1, b0 - q1 * b1    
    r0, r1 = r1, r0 % r1

print(a0, b0)

Solution (Python):
def extgcd(a, b, d=0):
    """solve ax + by = gcd(a, b)
       return x, y, gcd(a, b)
       unproved
    """
    g = a
    if b == 0:
        x, y = 1, 0
    else:
        x, y, g = extgcd(b, a % b)
        x, y = y,  x - a // b * y
    return x, y, g

a, b = map(int, input().split())
print(*extgcd(a, b)[:2])

Solution (Python):
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty)
a, b = map(int, raw_input().split())
ans = egcd(a, b)
for i in ans: print i,

Solution (Python):
def gcd(a, b):
    global queue
    r = a % b
    if r:
        d = a // b
        sb = queue.pop()
        sa = queue.pop()
        sc = tuple(map(lambda x, y: x - d * y, sa, sb))
        queue.append(sb)
        queue.append(sc)
        return gcd(b, r)
    else:
        return b


a, b = map(int, input().split())
queue = [(1, 0, a), (0, 1, b)]
g = gcd(a, b)
x, y, r = queue.pop()
print(x, y)

Solution (Python):
def gcd(a, b):
    global queue
    r = a % b
    if r:
        d = a // b
        sb = queue.pop()
        sa = queue.pop()
        queue.append(sb)
        queue.append(tuple(map(lambda x, y: x - d * y, sa, sb)))
        return gcd(b, r)
    else:
        return b


a, b = map(int, input().split())
queue = [(1, 0), (0, 1)]
g = gcd(a, b)
print(*queue.pop())

Solution (Python):
a, b = map(int, input().split())

r0 = a
r1 = b
x0 = 1
x1 = 0
y0 = 0
y1 = 1
while r1 > 0:
    q1 = r0 // r1
    r2 = r0 % r1
    x2 = x0 - q1 * x1
    y2 = y0 - q1 * y1
    r0 = r1
    r1 = r2
    x0 = x1
    x1 = x2
    y0 = y1
    y1 = y2
print(x0,y0)

Solution (Python):
import fractions
def myegcd(a,b):
    x1 = 1
    y1 = 0
    z1 = a
    x2 = 0
    y2 = 1
    z2 = b
    while z2!=fractions.gcd(a,b):
        if z2==0:
            break
        q = (z1-(z1%z2))/z2
        x1 = x1 -(q*x2)
        y1 = y1 -(q*y2)
        z1 = z1 -(q*z2)

        t = x1
        x1 = x2
        x2 = t

        t = y1;
        y1 = y2;
        y2 = t;

        t = z1;
        z1 = z2;
        z2 = t;
    return x2,y2

p,q = map(int,raw_input().split())
ans1,ans2 = myegcd(p,q)
print ans1,ans2

Solution (Python):
def extgcd(a, b):
    if b:
        d, y, x = extgcd(b, a%b)
        y -= (a/b)*x
        return d, x, y
    else:
        return a, 1, 0
d, x, y = extgcd(*map(int, raw_input().split()))
print x, y

Solution (Python):




"""
input:
3 8

output:
3 -1
"""

import sys


def ext_euclid(a, b):
    if b == 0:
        return 1, 0
    else:
        x, y = ext_euclid(b, a % b)
        x, y = y, (x - (a // b) * y)
        return x, y


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    n1, n2 = map(int, _input[0].split())
    print(*ext_euclid(n1, n2))

Solution (Python):
a,b=map(int,input().split())
c=g=1;e=f=0
while b:
    d,m=divmod(a,b)
    h=c-d*e
    i=f-d*g
    a,b=b,m
    c,e=e,h
    f,g=g,i
print(c,f)

Solution (Python):
r0, r1 = map(int, input().split())
a0, a1 = 1, 0
b0, b1 = 0, 1
while 0 < r1:
    q1 = r0 // r1
    a0, a1 = a1, a0 - q1 * a1
    b0, b1 = b1, b0 - q1 * b1    
    r0, r1 = r1, r0 % r1
 
print(a0, b0)

Solution (Python):

from __future__ import print_function


def rec(a, b):
    """a * x + b * y = gcd(a, b) ??¨??????????????? (x, y, gcd) ?????????"""
    assert a >= b
    q, r = divmod(a, b)
    if r == 0:
        return 0, 1, b
    x, y, gcd = rec(b, r)
    
    
    
    return y, x - q * y, gcd


a, b = [int(_) for _ in raw_input().split()]

if a < b:
    y0, x0, gcd = rec(b, a)
else:
    x0, y0, gcd = rec(a, b)



dx = b // gcd
dy = -a // gcd
if dx < 0:
    dx = -dx
    dy = -dy
x = x0
y = y0
mag = abs(x) + abs(y)

while True:
    x1 = x + dx
    y1 = y + dy
    mag1 = abs(x1) + abs(y1)
    if mag1 >= mag:
        break
    mag = mag1
    x = x1
    y = y1

while True:
    x1 = x - dx
    y1 = y - dy
    mag1 = abs(x1) + abs(y1)
    if mag1 > mag:
        break
    mag = mag1
    x = x1
    y = y1

print(x, y)

Solution (Python):
r0, r1 = map(int, input().split())
a0, a1 = 1, 0
b0, b1 = 0, 1
while 0 < r1:
    q1 = r0 // r1
    a0, a1 = a1, a0 - q1 * a1
    b0, b1 = b1, b0 - q1 * b1    
    r0, r1 = r1, r0 % r1
  
print(a0, b0)

Solution (Python):



DEBUG = False

def dbg(*args):
    if DEBUG:
        print(*args)

def extgcd(a, b):
    if b == 0:
        return a, 1, 0
    else:
        d, xprime, yprime = extgcd(b, a % b)
        x = yprime
        y = xprime - (a//b) * yprime
        return d, x, y

def main():
    a, b = map(int, input().split())
    dbg("a:{}, b:{}".format(a, b))

    d, x, y = extgcd(a, b)
    print("{} {}".format(x, y))

if __name__ == "__main__": main()

Solution (Python):


import itertools
import sys, math, os


PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input2.txt", "rt")


def extended_gcd(a, b):
    s, old_s = 0, 1
    t, old_t = 1, 0
    r, old_r = b, a
    while r != 0:
        q = old_r // r
        old_r, r = r, old_r - q * r
        old_s, s = s, old_s - q * s
        old_t, t = t, old_t - q * t
    return old_r, old_s, old_t

a, b = [int(_) for _ in input().split()]
g, x, y = extended_gcd(a, b)
print(x, y)

Solution (Python):
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def solve():
    a, b = map(int, input().split())
    if a == b or a % b == 0:
        print(0, 1)
    elif b % a == 0:
        print(1, 0)
    else:
        g = gcd(a, b)
        a //= g
        b //= g
        coe = [[1, 0], [0, 1]]
        while b != 1:
            quo = a // b
            coe_d1 = coe[1]
            coe_d2 = [coe[0][0] - coe[1][0] * quo, coe[0][1] - coe[1][1] * quo]
            coe = [coe_d1, coe_d2]
            a, b = b, a % b
        print(*coe[1])

solve()

Solution (Python):
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def solve():
    a, b = map(int, input().split())
    if a == b or a % b == 0:
        print(0, 1)
    elif b % a == 0:
        print(1, 0)
    else:
        g = gcd(a, b)
        a //= g
        b //= g
        coe = [[1, 0], [0, 1]]
        while b != 1:
            quo = a // b
            coe_d1 = coe[1]
            coe_d2 = [coe[0][0] - coe[1][0] * quo, coe[0][1] - coe[1][1] * quo]
            coe = [coe_d1, coe_d2]
            a, b = b, a % b
        print(*coe[1])

solve()

Solution (Python):
def solve():
    a, b = map(int, input().split())
    s_i, s_j = 1, 0
    t_i, t_j = 0, 1
    while b:
        q, r = divmod(a, b)
        s_i, s_j = s_j, s_i - q * s_j
        t_i, t_j = t_j, t_i - q * t_j
        a, b = b, r
    print(s_i, t_i)

solve()

Solution (Python):
def solve():
    a, b = map(int, input().split())
    s_i, s_j = 1, 0
    t_i, t_j = 0, 1
    while b:
        q, r = divmod(a, b)
        s_i, s_j = s_j, s_i - q * s_j
        t_i, t_j = t_j, t_i - q * t_j
        a, b = b, r
    print(s_i, t_i)

solve()

Solution (Python):
def solve():
    a, b = map(int, input().split())
    s_i, s_j = 1, 0
    t_i, t_j = 0, 1
    while b:
        q, r = divmod(a, b)
        s_i, s_j = s_j, s_i - q * s_j
        t_i, t_j = t_j, t_i - q * t_j
        a, b = b, r
    print(s_i, t_i)

solve()

Solution (Python):
def solve():
    a, b = map(int, input().split())
    s_i, s_j = 1, 0
    t_i, t_j = 0, 1
    while b:
        q, r = divmod(a, b)
        s_i, s_j = s_j, s_i - q * s_j
        t_i, t_j = t_j, t_i - q * t_j
        a, b = b, r
    print(s_i, t_i)

solve()

Solution (Python):
def solve():
    a, b = map(int, input().split())
    s_i, s_j = 1, 0
    t_i, t_j = 0, 1
    while b:
        q, r = divmod(a, b)
        s_i, s_j = s_j, s_i - q * s_j
        t_i, t_j = t_j, t_i - q * t_j
        a, b = b, r
    print(s_i, t_i)

solve()

Solution (Python):
import sys
a1,b1 = list(map(int,input().split()))
x1 = 0
y1 = 0
d = 0
def exgcd(a,b):
    global x1,y1,d
    if b == 0:
        x1 = 1
        y1 = 0
        return a
    else:
        d = exgcd(b,a%b)
        tmp = x1
        x1 = y1
        y1 = tmp - a//b*y1
        


exgcd(a1,b1)
print(x1,y1)

Solution (Python):
def solve():
    a, b = map(int, input().split())
    s_i, s_j = 1, 0
    t_i, t_j = 0, 1
    while b:
        q, r = divmod(a, b)
        s_i, s_j = s_j, s_i - q * s_j
        t_i, t_j = t_j, t_i - q * t_j
        a, b = b, r
    print(s_i, t_i)

solve()

Solution (Python):
r,s=map(int,input().split())
a=d=1;b=c=0
while s:q=r//s;r,s,a,c,b,d=s,r%s,c,a-q*c,d,b-q*d;
print(a,b)

Solution (Python):
r,s=map(int,input().split())
a=d=1;b=c=0
while s:q=r//s;r,s,a,c,b,d=s,r%s,c,a-q*c,d,b-q*d
print(a,b)

Solution (Python):
def extecd(b, n):
    x0, x1, y0, y1 = 1, 0, 0, 1
    while n != 0:
        q, b, n = b // n, n, b % n
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    print(x0, y0)

def main():
    a, b = input().split()
    a = int(a)
    b = int(b)
    extecd(a, b)

main()

Solution (Python):
def gcd(a, b):
    x, y = [a, b] if a > b else [b, a]
    while y:
        x, y = y, x%y
    return x

def solve(a, b):
    if b == 1:
        return 0, 1
    elif a == 1:
        return 1, 0

    A, B, Q, R = [a], [b], [b//a], [b%a]
    i = 0
    while R[i] != 0:
        B.append(A[i])
        A.append(R[i])
        Q.append(B[i+1]//A[i+1])
        R.append(B[i+1]%A[i+1])
        i += 1

    x, y = -1*Q[len(Q)-2], 1
    for i in range(len(A)-3, -1, -1):
        x, y = y - x*Q[i], x

    return x, y

a, b = list(map(int, input().split(' ')))
c = gcd(a, b)
a, b = a//c, b//c

x, y = solve(a,b)
print(x, y)

Solution (Python):
def extended_euclid(a,b):
	c = g = 1
	e = f = 0
	while b:
		div,mod = divmod(a,b)
		h = c - div * e
		i = f - div * g
		a,b = b,mod
		c,e = e,h
		f,g = g,i

	return (c,f)
n,m = map(int,input().split(" "))
print(*extended_euclid(n,m))

Solution (Python):

def e_gcd(a, b):
    u0,u1 = 1,0
    if b == 0:
    	return u0,u1
   
    d0,d1 = a,b
    while True:
        q,r = d0//d1,d0%d1
        if r == 0:
        	return u1,(d1-a*u1)/b

        d0,d1 = d1,r 
        u0,u1 = u1,u0-q*u1 

a,b = map(int, raw_input().split())
print " ".join(map(str, e_gcd(a,b)))

Solution (Python):


def ex_gcd(a, b):
    '''
    ax + by = gcd(a, b) の整数解を求める
    '''
    if b == 0:
        return 1, 0
    else:
        x, y = ex_gcd(b, a%b)
        return y, x - (a // b) * y

n, m = map(int, input().split())
res1, res2 = ex_gcd(n, m)
print(res1, res2)

Solution (Python):
from math import gcd
def gcd_ext(a, b):
  x,y,lastx,lasty = 0,1,1,0
  while b!=0:
    q=a//b
    a,b=b,a%b
    x,y,lastx,lasty=lastx-q*x,lasty-q*y,x,y
  return (lastx,lasty)
a,b=map(int,input().split())
c=gcd(a,b)
a,b=a//c,b//c
x,y=gcd_ext(a,b)
ans=[(x,y)]
for i in [-1,0,1]:
  ans+=[(-b*i+x,a*i+y)]
print(*min(ans,key=lambda x:abs(x[0])+abs(x[1])))

Solution (Python):
def extgcd(a, b):
    if b == 0:
        return a, 1, 0
    else:
        g, x, y = extgcd(b, a % b)
        return g, y, x - (a // b) * y

a, b = map(int, input().split())
_, x, y = extgcd(a, b)
print(x, y)

Solution (Python):
r,s=map(int,input().split())
a = 1
d = 1
b = 0
c = 0
while s:
    q=r//s
    
    ss = s
    rr = r
    aa = a
    bb = b
    cc = c
    dd = d
    
    r = ss
    s = rr % ss
    a = cc
    c = aa - q * cc
    b = dd
    d = bb - q * dd
print(a,b)

Solution (Python):
def modinv(a, m):
    b, u, v = m, 1, 0
    while(b):
        a, b, u, v = b, a%b, v, u-(a//b)*v
    return u % m

def gcd_base(x, y):
    if x % y:
        return gcd_base(y, x%y)
    return y

a, b = map(int, input().split())
a1 = a//gcd_base(a,b)
b1 = b//gcd_base(a,b)
x = modinv(a1, b1)
y = (1-a1*x)//b1
if abs(x)+abs(y) < abs(x-b1)+abs(y+a1):
    print(x, y)
elif abs(x)+abs(y) > abs(x-b1)+abs(y+a1):
    print(x-b1, y+a1)
elif x <= y:
    print(x, y)
else:
    print(x-b1, y+a1)

Solution (Python):
def ext_euclid(a, b):
    
    x0, y0, r0 = 1, 0, a
    x1, y1, r1 = 0, 1, b
    while r0 != 0:
        x0, y0, r0, x1, y1, r1 = x1 - x0 * (r1 // r0), y1 - y0 * (
            r1 // r0), r1 % r0, x0, y0, r0
    if a * x1 + b * y1 == 1:
        return x1, y1


def gcd(a, b):
    while a:
        a, b = b % a, a
    return b


a, b = map(int, input().split())
g = gcd(a, b)
a, b = a // g, b // g
x, y = ext_euclid(a, b)
if a == b and x > y:
    x, y = y, x
print(x, y)

Solution (Python):
a,s=map(int,input().split())
def ex_euclid(x, y):
    c0, c1 = x, y
    a0, a1 = 1, 0
    b0, b1 = 0, 1
    while c1 != 0:
        m = c0 % c1
        q = c0 // c1
        c0, c1 = c1, m
        a0, a1 = a1, (a0 - q * a1)
        b0, b1 = b1, (b0 - q * b1)
    return c0, a0, b0
print(*ex_euclid(a,s)[1:3],sep=" ")

Solution (Python):
a,b = map(int,input().split())
def extgcd(a,b):
    if b:
        y,x = extgcd(b,a%b)
        y -= (a//b)*x
        return x,y
    else:
        return 1,0

x,y = extgcd(a,b)
print(" ".join([str(x),str(y)]))

Solution (Python):
import math
a,b=map(int,input().split())
x=[0]
y=[0]
def extgcd(a,b,x,y):
    d=a
    if b!=0:
        d=extgcd(b,a%b,y,x)
        y[0]-=(a//b)*x[0]
    else:
        x[0]=1
        y[0]=0

extgcd(a,b,x,y)
print(x[0],y[0])

Solution (Python):
def ExtendedGCD(a, b, x, y):
    """
    ax + by = gcd(a, b)となる(y, x)の組,gcd(a,b)を返す
    """
    if b == 0:
        return 0, 1, a
    x, y, g = ExtendedGCD(b, a % b, y, x)
    return y - (a // b) * x, x, g


if __name__ == "__main__":
    a, b = map(int, input().split())
    y, x, gcd = ExtendedGCD(a, b, 0, 0)
    print(x, y)

Solution (Python):
import sys,bisect,math
from functools import reduce
sys.setrecursionlimit(15000)

A,B = map(int,sys.stdin.readline().split())

def exgcd0(x,y):
  
  
  a0,b0,r0=1,0,x
  a1,b1,r1=0,1,y
  while r1 > 0:
    q1=r0//r1
    r2=r0%r1
    a2=a0-q1*a1
    b2=b0-q1*b1
    a0,b0,r0=a1,b1,r1
    a1,b1,r1=a2,b2,r2
  return a0,b0,r0

def exgcd(a,b):
  if b==0:
    return 1,0,a
  else:
    q=a//b
    r=a%b
    s1,t1,c = exgcd(b,r)
    s = t1
    t = s1-t1*q
    return s,t,c

ret = exgcd0(A,B)
print(ret[0],ret[1])

Solution (Python):
def eGCD(a,b):
    if b==0:
        return a,1,0
    else:
        g,x,y=eGCD(b,a%b)
        return g,y,x-a//b*y

a,b=map(int,input().split())
gcd,x,y=eGCD(a,b)
print(x,y)

Solution (Python):
a,b = map(int,input().split())

def myoutput(ls):
    if len(ls)==0:
        print(" ")
    elif type(ls[0])==str:
        print(" ".join(ls))
    elif type(ls[0])==int:
        print(" ".join(map(str,ls)))
    else:
        print("Output Error")

from collections import defaultdict,Counter




def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        x -= (b // a) * y
        return g, x, y

if a==b:
    
    print(0,1)
    exit()
else:
    g,x,y = egcd(a,b)
    myoutput([x,y])
    exit()

Solution (Python):
def ex_euclid(x, y):
    c0, c1 = x, y
    a0, a1 = 1, 0
    b0, b1 = 0, 1
 
    while c1 != 0:
        m = c0 % c1
        q = c0 // c1
 
        c0, c1 = c1, m
        a0, a1 = a1, (a0 - q * a1)
        b0, b1 = b1, (b0 - q * b1)
 
    return c0, a0, b0

a,b = map(int,input().split())
c,a,b = ex_euclid(a,b)
print(a,b)

Solution (Python):
def extgcd(a, b):
    if b == 0:
        return a, 1, 0
    else:
        d, y, x = extgcd(b, a%b)
        y -= a // b * x
        return d, x, y
a, b = map(int, input().split())
_, x, y = extgcd(a, b)
print(x, y)

Solution (Python):



a, b = map(int, input().split())

def extgcd(a, b):
    d = a
    if b != 0:
        d, xprime, yprime = extgcd(b, a % b)
        x = yprime
        y = xprime - (a // b) * yprime
    else:
        x = 1
        y = 0
    return d, x, y

_, x, y = extgcd(a, b)
print(f"{x} {y}")

Solution (Python):
import math
a, b = map(int, input().split())
c = math.gcd(a, b)

def ex_euclid(x, y):
  c0, c1 = x, y
  a0, a1 = 1, 0
  b0, b1 = 0, 1

  while c1 != 0:
      m = c0 % c1
      q = c0 // c1

      c0, c1 = c1, m
      a0, a1 = a1, (a0 - q * a1)
      b0, b1 = b1, (b0 - q * b1)

  return c0, a0, b0

_, a, b = ex_euclid(a, b)
print(a, b)

Solution (Python):
import sys
sys.setrecursionlimit(200000000)

A, B = map(int, input().split())

def extgcd(a, b, x, y):
    d = a
    if b != 0:
        y, x = extgcd(b, a % b, y, x)
        y -= (a // b) * x
        return x, y
    else:
        return (1, 0)

x, y = extgcd(A, B, 0, 0)
print("{} {}".format(x, y))

Solution (Python):
a,b = map(int,input().split())

def ExtGCD(a,b): 
    flag = True
    if a < b:
        a,b = b,a
        flag = False
    r0, r1, s0, s1, t0, t1 = a, b, 1, 0, 0, 1
    while r1 != 0:
        q, r2 = r0//r1, r0%r1
        r0, s0, t0, r1, s1, t1 = r1, s1, t1, r2, s0-s1*q,t0-t1*q
    d = r0
    if flag :
        return (d,s0,t0)
    else:
        return (d,t0,s0)

print(str(ExtGCD(a,b)[1])+" "+str(ExtGCD(a,b)[2]))

Solution (Python):
def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
    gcd = b
    return gcd,x,y

a,b = (int(_) for _ in input().split(" "))
gcd,x,y = egcd(a,b)

if y * a + x * b == gcd:
    tmp = x
    x = y
    y = tmp

print(x,y)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)




a, b = map(int, input().split())


def extgcd(a, b):
    if b == 0:
        return a, 1, 0

    p, q = a // b, a % b
    d, x, y = extgcd(b, q)
    x, y = y, x - p * y
    return d, x, y


reverse = False
if b > a:
    a, b = b, a
    reverse = True

d, x, y = extgcd(a, b)

if reverse:
    x, y = y, x

print(x, y)

Solution (Python):
def ex_euclid(x,y):
    c0,c1 = x,y
    a0,a1 = 1,0
    b0,b1 = 0,1
    while c1:
        a0,a1 = a1,a0-c0//c1*a1
        b0,b1 = b1,b0-c0//c1*b1
        c0,c1 = c1,c0%c1
    return c0,a0,b0

x,y = map(int,input().split())
c,a,b = ex_euclid(x,y)
print(a,b)

Solution (Python):
def gcd(a,b):
	if b>a:
		a,b = b,a
	r = a%b
	if r==0:
		return b
	else:
		return gcd(b, a%b)

def solve(a,b):
	if a==1:
		return 1,0
	if b==1:
		return 0,1
	if a>b:
		q = a//b
		r = a%b
		x, y = solve(r,b)
		return x, y-q*x
	if a<b:
		q = b//a
		r = b%a
		x, y = solve(a,r)
		return x-q*y, y

a,b = map(int, input().split())
g = gcd(a,b)
a//=g
b//=g
x, y = solve(a,b)

def p(n):
	return x+b*n
def q(n):
	return y-a*n

def f(n):
	return abs(p(n))+abs(q(n))

if a>b:
	n = y//a
	nn = n 
	m = f(n)
	if f(n-1) < m:
		nn = n-1
		m = f(n-1)
	if f(n+1) < m:
		nn = n+1
		m = f(n+1)
	x = p(nn)
	y = q(nn)
elif a<b:
	n = -x//b
	nn = n 
	m = f(n)
	if f(n-1) < m:
		nn = n-1
		m = f(n-1)
	if f(n+1) < m:
		nn = n+1
		m = f(n+1)
	x = p(nn)
	y = q(nn)
else:
	x = 0
	y = 1

print("{} {}".format(x,y))

Solution (Python):
from functools import lru_cache

@lru_cache()
def GCD(a,b):
    if min(a,b)==0:
        return max(a,b)
    else:
        return GCD(min(a,b),max(a,b)%min(a,b))

def extendedEuler(a,b):
    if b==GCD(a,b):
        return (0,1)
    elif a==GCD(a,b):
        return (1,0)

    if a<b:
        X,Y=extendedEuler(a,b%a)
        return (X-(b//a)*Y,Y)
    else:
        X,Y=extendedEuler(a%b,b)
        return (X,Y-(a//b)*X)

a,b=[int(i) for i in input().split(" ")]
x0,y0=extendedEuler(a,b)
print(x0,y0)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect_left
from heapq import heappush, heappop

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

a, b = MAP()
c = gcd(a, b)

def extgcd(a, b, d=0):
    g = a
    if b == 0:
        x, y = 1, 0
    else:
        x, y, g = extgcd(b, a % b)
        x, y = y,  x - a // b * y
    return x, y, g

print(*extgcd(a, b)[:2])

Solution (Python):
def extgcd(a, b):
    x, y = 1, 0
    g, e = 1, 0
    while b != 0:
        q, r = divmod(a, b)
        m = x-q*e
        n = y-q*g
        a, b = b, r
        x, e = e, m 
        y, g = g, n 
    return x, y, g

a, b = map(int, input().split())
x, y, g = extgcd(a, b)

print(x, y)

Solution (Python):

a,b = map(int,input().split())

def extgcd(x,y):
    c1,c2 = x,y
    a1,a2 = 1,0
    b1,b2 = 0,1
    
    while c2:
        m = c1%c2
        q = c1//c2
        c1,c2 = c2,m
        a1,a2 = a2,(a1-q*a2)
        b1,b2 = b2,(b1-q*b2)
        
    return c1,a1,b1

ans = extgcd(a,b)
print(ans[1],ans[2])

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7


def extgcd(a, b, x, y):
    if b == 0:
        x = 1
        y = 0
        return (y, x)
    else:
        x, y = extgcd(b, a%b, y, x)
        y -= a // b * x
        return (y, x)

a, b = MAP()

y, x = extgcd(a, b, 0, 0)
print(x, y)

Solution (Python):
def ex_euclid(x, y):
	a0, a1 = 1, 0
	b0, b1 = 0, 1
	while y!=0:
		a0, a1 = a1, (a0 - x//y * a1)
		b0, b1 = b1, (b0 - x//y * b1)
		x, y = y, x%y
	return a0, b0

a,b=map(int,input().split())
print(*ex_euclid(a,b))

Solution (Python):
def extended_gcd(a, b):
    """ax + by = gcd(a, b)の整数解(x, y)を求める"""
    if b == 0:
        return a, 1, 0
    else:
        g, y, x = extended_gcd(b, a % b)
        y -= (a // b) * x
        return g, x, y

a, b = map(int, input().split())
_, x, y = extended_gcd(a, b)
print(x, y)

Solution (Python):
if __name__ == "__main__":
    a, b = list(map(lambda x: int(x), input().split()))
    c = g = 1
    e = f = 0
    while b:
        d, m = divmod(a, b)
        h = c - d * e
        i = f - d * g
        a, b = b, m
        c, e = e, h
        f, g = g, i
    print(c, f)

Solution (Python):
r,s=map(int,input().split())
a=d=1;b=c=0
while s:q=r//s;r,s,a,c,b,d=s,r%s,c,a-q*c,d,b-q*d
print(a,b)

Solution (Python):


L=input().split( )
a=[int(L[0]),1,0]
b=[int(L[1]),0,1]

while a[0]%b[0]!=0:
    k=a[0]//b[0]

    c=b[0]
    c1=b[1]
    c2=b[2]

    a[1]-=(k*b[1])
    a[2]-=(k*b[2])

    b[0]=a[0]%b[0]
    b[1]=a[1]
    b[2]=a[2]

    a[0]=c
    a[1]=c1
    a[2]=c2
    
k=a[0]//b[0]

c=b[0]
c1=b[1]
c2=b[2]

a[1]-=(k*b[1])
a[2]-=(k*b[2])

b[0]=a[0]%b[0]
b[1]=a[1]
b[2]=a[2]

a[0]=c
a[1]=c1
a[2]=c2

print(a[1],a[2])

Solution (Python):
a,b=map(int,input().split())
c=g=1;e=f=0
while b:
    d,m=divmod(a,b)
    h=c-d*e
    i=f-d*g
    a,b=b,m
    c,e=e,h
    f,g=g,i
print(c,f)

Solution (Python):
def E(a,b):
  c0,c1=a,b
  x0,x1=1,0
  y0,y1=0,1
  
  while c1!=0:
    m=c0%c1
    q=c0//c1
    c0,c1=c1,m
    x0,x1=x1,(x0-q*x1)
    y0,y1=y1,(y0-q*y1)
    
  return x0,y0
a,b=map(int,input().split())
print(*E(a,b)[:2])

Solution (Python):
def calc_gcd(x, y):
    
    if x < y:
        x, y = y, x

    while y > 0:
        x, y = y, x % y

    return x


a, b = map(int, input().split())

gcd = calc_gcd(a, b)

x1 = 1
y1 = 0
z1 = a_prime = a / gcd

x2 = 0
y2 = 1
z2 = b_prime = b / gcd

while z2 != 1:
    q = (z1 - (z1 % z2)) / z2

    (x1, y1, z1), (x2, y2, z2) = (x2, y2, z2), (x1 - (q * x2), y1 - (q * y2), z1 - (q * z2))


t = 0
x = x2 + b_prime * t
y = y2 + a_prime * t

print(int(x), int(y))

Solution (Python):
import math

def Euclid(a, b):
    if a == 0 and b > 0:
        return 0, 1
    r = q = 0
    x = y = 0
    if a >= b:
        r = a % b
        q = a // b
        x1, y1 = Euclid(r, b)
        x = x1
        y = y1 - q * x1
    else:
        r = b % a
        q = b // a
        x1, y1 = Euclid(r, a)
        x = y1 - q * x1
        y = x1
    return x, y

line = input()
a, b = list(map(int, line.split()))
x, y = Euclid(a, b)
if x > y:
    t = math.floor(- (x - y)/(a + b))
    x1 = b * t + x
    y1 = - a * t + y
    if abs(x) + abs(y) >= abs(x1) + abs(y1):
        x, y = x1, y1
print(x, y)

Solution (Python):
def exgcd(x,y):
  a0,a1=1,0
  b0,b1=0,1
  while y>0:
    q=x//y
    a2=a0-q*a1
    b2=b0-q*b1
    x,y=y,x%y
    a0,a1=a1,a2
    b0,b1=b1,b2
  return [a0,b0]
  
x,y=map(int,input().split())
ans=exgcd(x,y)
print(ans[0],ans[1])

Solution (Python):
def extgcd(a, b, d = 0):
    g = a
    if b == 0:
        x, y = 1, 0
    else:
        x, y, g = extgcd(b, a%b)
        x, y = y, x - a//b *y
    return x,y,g
a, b = map(int, input().split())
print(*extgcd(a, b)[:2])

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007


def gcd(a,b):
    if a==0:
        return b
    return gcd(b%a,a)
a,b = LI()
g = gcd(a,b)
a//=g
b//=g
if b == 1:
    print(0,1)
    quit()
if b < 4:
    f = b-1
else:
    p = []
    x = 2
    m = b
    while x**2 <= b:
        if not m%x:
            p.append(x)
            while not m%x:
                m//=x
        x += 1
    if m != 1:p.append(m)
    f = b
    for i in p:
        f *= (1-1/i)
    f = int(f)
x_ = pow(a,f-1,b)
y_ = (1-a*x_)//b
ans = [x_,y_,abs(x_)+abs(y_)]
for i in range(-100,100):
    s = -b*i+x_
    t = a*i+y_
    m = abs(s)+abs(t)
    if m < ans[2]:
        ans = [s,t,m]
    elif m == ans[2] and s <= t:
        ans = [s,t,m]
print(ans[0],ans[1])

Solution (Python):
def ex_euclid(x, y):
    c0, c1 = x, y
    a0, a1 = 1, 0
    b0, b1 = 0, 1

    while c1 != 0:
        m = c0 % c1
        q = c0 // c1
        c0, c1 = c1, m
        a0, a1 = a1, (a0 - q * a1)
        b0, b1 = b1, (b0 - q * b1)

    return c0, a0, b0


a, b = map(int, input().split())
ans = ex_euclid(a, b)
print(ans[1], ans[2])

Solution (Python):
def exgcd(n1,n2): 
    x1,y1,m1 = (1,0,n1)
    x2,y2,m2 = (0,1,n2)
    while( n2 != 0):
        t = n1 // n2
        if (m1 >= m2):
            x1 -=  (x2 * t)
            y1 -=  (y2 * t)
            m1 -=  (m2 * t)
        else:
            x2 -= (x1 * t)
            y2 -= (y1 * t)
            m2 -= (m1 * t)
        i = n2
        n2 = n1 % n2
        n1 = i
    if (m1 == 1):return x1,y1
    return x2,y2

(m,n)  =  map(int,input().split())
(a1,b1) =  exgcd(m,n)
(a2,b2) =  exgcd(n,m)


if (abs(a1)+abs(b1) < abs(a2) + abs(b2)):
    print(a1,b1)
elif (abs(a1)+abs(b1) > abs(a2) + abs(b2)):
    print(b2,a2)
else:
    if (b1 >= a1):
        print(a1,b1)
    else:
        print(b2,a2)