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 ≤ 109
	

Sample Input 1

4 12

Sample Output 1

1 0

Sample Input 2

3 8

Sample Output 2

3 -1



Sample input:
4 12


Sample output:
1 0

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys


REC_LIM = 10000


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


def main():
    sys.setrecursionlimit(REC_LIM)
    _, x, y = extgcd(*map(int, input().split()))
    print("{} {}".format(x, y))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


# Based on
# https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm
def extgcd(a, b):
    x, y, u, v = 0, 1, 1, 0
    while a:
        q, r = divmod(b, a)
        m, n = x - u * q, y - v * q
        b, a, x, y, u, v = a, r, u, v, m, n
    return b, x, y


def main():
    _, x, y = extgcd(*map(int, input().split()))
    print("{} {}".format(x, y))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat May  7 22:31:12 2016

@author: kt
"""
def gcd(a,b): #?????§??¬?´???°???????????°??????
    r=0
    while True:
       r=a%b
       if r==0:
           break
       a=b
       b=r
    return b


a, b = map(int, input().split(" "))
g=gcd(a,b)
a=a/g
b=b/g
c=0
x1=1
x2=0
z1=a
y1=0
y2=1
z2=b
q=0

while True:
    if z2==1:
        break    
    q = (z1 - (z1 % z2)) / z2
    x3=(x1-q*x2)
    y3=(y1-q*y2)
    z3=z1-q*z2
    x1=x2
    x2=x3
    y1=y2
    y2=y3
    z1=z2
    z2=z3
   
if x3>y3:
    temp=y3
    y3=x3
    x3=temp
print ("%d %d" % (int(x3), int(y3)))

Submission status: Wrong Answer

Solution code:
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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
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)
    # a = b * q + r
    # b * x + r * y = gcd
    # a * y + b * (x - q * y) = gcd
    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)

# a/gcd * (x - x0) = -b/gcd * (y - y0)
# x = x0 + (-b/gcd) * k, y = y0 + a/gcd * k
dx = -b // gcd
dy = a // gcd
x = x0
y = y0
mag = abs(x) + abs(y)

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

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

print(x, y)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
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)
    # a = b * q + r
    # b * x + r * y = gcd
    # a * y + b * (x - q * y) = gcd
    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)

# a/gcd * (x - x0) = -b/gcd * (y - y0)
# x = x0 + (-b/gcd) * k, y = y0 + a/gcd * k
dx = -b // gcd
dy = a // gcd
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)

Submission status: Wrong Answer

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

def solve():
    #a, b = map(int, input().split())
    a,b = 999999937, 123
    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()

Submission status: Wrong Answer

Solution code:
import math
a,b=map(int,input().split())
c=math.gcd(a,b)
for x in range(b):
 y=(c-a*x)/b
 if int(y)==y:x=x;print(y);break
print(x,y)

Submission status: Wrong Answer

Solution code:
import math
a,b=map(int,input().split())
c=math.gcd(a,b)
for x in range(b):
 y=(c-a*x)/b
 if int(y)==y:break
print(x,int(y))

Submission status: Wrong Answer

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

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

x = 0
y = None
while True:
    tmp = (1-a*x)/b
    if tmp == int(tmp):
        y = int(tmp)
        break
    x += 1

print(x, y)

Submission status: Wrong Answer

Solution code:
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 a == 1:
        return 1, 0
    elif b == 1:
        return 0, 1

    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)

Submission status: Time Limit Exceeded

Solution code:
# coding=utf-8


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 = 0
    while True:
        if (1+number1*answer1) % number2 == 0:
            return -answer1, (1+number1*answer1)//number2
        answer1 += 1


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)):
        return modify_solution(x_sp_s + n2, y_sp_s - 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)
    x_sp, y_sp = modify_solution(x_sp, y_sp, a, b)
    print(x_sp, y_sp)

Submission status: Time Limit Exceeded

Solution code:
# coding=utf-8


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


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)):
        return modify_solution(x_sp_s + n2, y_sp_s - 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)
    x_sp, y_sp = modify_solution(x_sp, y_sp, a, b)
    print(x_sp, y_sp)

Submission status: Time Limit Exceeded

Solution code:
# coding=utf-8


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


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)
    x_sp, y_sp = modify_solution(x_sp, y_sp, a, b)
    print(x_sp, y_sp)

Submission status: Time Limit Exceeded

Solution code:
import math
a,b=map(int,input().split())
c=math.gcd(a,b)
for x in range(b):
 y=(c-a*x)/b
 if int(y)==y:break
f=lambda x,y:abs(x)+abs(y)
if f(x,y)<f(-b+x,a+y):
 print(x,int(y))
else:
 print(-b+x,int(a+y))

Submission status: Time Limit Exceeded

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

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

x = 0
y = None
while True:
    tmp = (1-a*x)/b
    if tmp == int(tmp):
        y = int(tmp)
        break
        
    x *= -1
    tmp = (1-a*x)/b
    if tmp == int(tmp):
        y = int(tmp)
        break
    x *= -1
    x += 1

print(x, y)

Submission status: Accepted

Solution code:
# coding=utf-8


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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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,

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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())

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


"""
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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)
    # a = b * q + r
    # b * x + r * y = gcd
    # a * y + b * (x - q * y) = gcd
    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)

# -a/gcd * (x - x0) = b/gcd * (y - y0)
# x = x0 + (b/gcd) * k, y = y0 + (-a/gcd) * k
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

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()

Submission status: Accepted

Solution code:
# Aizu Problem NTL_1_E: Extended Euclid Algorithm
#
import itertools
import sys, math, os

# read input:
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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
        #print(x1,y1,d)


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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
# read www.u.dendai.ac.jp/~ochi/introalg02.pdf if you need
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 # r=d0%d1. here is nomal gcd ope.
        u0,u1 = u1,u0-q*u1 # u1 = u0-d0//d1*u1. 

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

Submission status: Accepted

Solution code:
# Ex_Euclidean Algorithm

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)

Submission status: Accepted

Solution code:
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])))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
def ext_euclid(a, b):
    # 互いに素なa,bに対して、方程式ax+by=1の整数解を1つ求める
    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)

Submission status: Accepted

Solution code:
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=" ")

Submission status: Accepted

Solution code:
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)]))

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

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

def exgcd0(x,y):
  # if x < y:
  #   x,y = y,x
  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#a,b,c

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])

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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
# from math import gcd

# 拡張ユークリッド互除法
# gcd(a,b) と ax + by = gcd(a,b) の最小整数解を返す
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/problems/NTL_1_E
# 拡張ユークリッドの互除法

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}")

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

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

def ExtGCD(a,b): #ax+by=GCD(a,b)の解(x,y)
    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]))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

# 拡張Euclidの互除法
# 拡張ユークリッドの互除法

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)