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: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

# 拡張ユークリッドの互除法(ax+by=gcd(a, b)の解を求める)
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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#AOJのコース用からJOI2006用に編集

L=input().split( )
a=[int(L[0]),1,0]#gcd途中の余り、その余りをka+lbと表したk,l
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
    #print(a,b)
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,b)
print(a[1],a[2])

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
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

#拡張ユークリッドとかしらないので、オイラー関数でmodの逆元計算して無理やり通します。
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])

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())
ans = ex_euclid(a, b)
print(ans[1], ans[2])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

# Set max recursion limit
sys.setrecursionlimit(1000000)


def li_input():
    return [int(_) for _ in input().split()]

# Extended GCD
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)

def modinv(a, m):
    (inv, q, gcd_val) = egcd(a, m)
    return inv, q

def main():
    a, b = li_input()
    x, y = modinv(a, b)
    print(x, y)


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 = m // n
        x1, y1, m, x2, y2, n = x2, y2, n, x1 - q * x2, y1 - q * y2, m - q * n
    return x2, y2  # , n
print(*extended_euclid(*map(int, input().split())))

Submission status: Runtime Error

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:
        reverse_flag = 1
        n1, n2 = number2, number1
    else:
        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):
    if x_sp_s > y_sp_s:
        m2 = x_sp_s//n2
        return modify_solution(x_sp_s - (m2+1)*n2, y_sp_s + (m2+1)*n1, 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: Runtime Error

Solution code:
import sys

def sieve(n):
    is_prime = [True] * (n + 1)
    prime_list = []
    
    is_prime[0] = is_prime[1] = False
    prime_list.append(2)
    
    for i in range(3, n + 1, 2):
        if is_prime[i]: prime_list.append(i)
        for j in range(i * i, n + 1, i):
            is_prime[j] = False
    return prime_list
    
primes = sieve(40000)

def factoriaztion(n):
    ret = []
    for prime in primes:
        while n % prime == 0:
            ret.append(prime)
            n /= prime
        if n == 1: break
    if n > 1: ret.append((n, 1))
    return ret
    
    
if __name__ == '__main__':
    n = sys.stdin.readline()
    n = int(n)
    factors = factoriaztion(n)
    factors = itertools.groupby(factors)
    
    ans = 1
    
    for k, v in factors:
        l = len(list(v))
        ans = ans * (k ** l - k ** (l - 1))
    
    sys.stdout.write(str(ans) + '\n')

Submission status: Runtime Error

Solution code:
import sys
import itertools

def sieve(n):
    is_prime = [True] * (n + 1)
    prime_list = []
    
    is_prime[0] = is_prime[1] = False
    prime_list.append(2)
    
    for i in range(3, n + 1, 2):
        if is_prime[i]: prime_list.append(i)
        for j in range(i * i, n + 1, i):
            is_prime[j] = False
    return prime_list
    
primes = sieve(40000)

def factoriaztion(n):
    ret = []
    for prime in primes:
        while n % prime == 0:
            ret.append(prime)
            n /= prime
        if n == 1: break
    if n > 1: ret.append((n, 1))
    return ret
    
    
if __name__ == '__main__':
    n = sys.stdin.readline()
    n = int(n)
    factors = factoriaztion(n)
    factors = itertools.groupby(factors)
    
    ans = 1
    
    for k, v in factors:
        l = len(list(v))
        ans = ans * (k ** l - k ** (l - 1))
    
    sys.stdout.write(str(ans) + '\n')

Submission status: Runtime Error

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:
    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 a*x3+b*y3==1:
        break
    
print ("%d %d" % (int(x3), int(y3)))

Submission status: Runtime Error

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:
    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 a*x3+b*y3==1:
        break
    
print ("%d %d" % (int(x3), int(y3)))

Submission status: Runtime Error

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:
    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 z2==1:
        break
    
print ("%d %d" % (int(x3), int(y3)))

Submission status: Runtime Error

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
   
    
print ("%d %d" % (int(x3), int(y3)))

Submission status: Runtime Error

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 and a==b:
    temp=y3
    y3=x3
    x3=temp
print ("%d %d" % (int(x3), int(y3)))

Submission status: Runtime Error

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, a
    else:
        x, y, q = 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: Runtime Error

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:
        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: Runtime Error

Solution code:
r,s=map(int,input().split())
a=d=1,b=c=0
while r: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: Runtime Error

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