We already know Basic Euclidean Algorithm. Now using the Extended Euclidean Algorithm, given a and b calculate the GCD and integer coefficients x, y. Using the same. x and y must satisfy the equation ax + by = gcd(a, b) .
 
Example 1:
Input:
a = 35
b = 15
Output:
5 1 -2
Explanation:
gcd(a,b) = 5
35*1 + 15*(-2) = 5
Example 2:
Input:
a = 30
b = 20
Output:
10 1 -1
Explanation:
gcd(30,20) = 10
30*(1) + 20*(-1) = 10
Your Task:
You don't need to read input or print anything. Your task is to complete the function gcd() which takes an integer N as input parameters and returns array of three numbers containing gcd, x, y in the same order.
 
Expected Time Complexity: O(log max(a,b))
Expected Space Complexity: O(1)
 
Constraints:
1 <= a,b <= 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3

class Solution:
    def gcd(self, a,b):
        # code here

Solutions:
class Solution:

	def gcd(self, a, b):
		(r, r0) = (a, b)
		(s, s0) = (1, 0)
		(t, t0) = (0, 1)
		while r0 != 0:
			q = r // r0
			(r, r0) = (r0, r - q * r0)
			(s, s0) = (s0, s - q * s0)
			(t, t0) = (t0, t - q * t0)
		d = r
		return (d, s, t)


class Solution:

	def gcd(self, a, b):
		if b == 0:
			return (a, 1, 0)
		(gcd1, x1, y1) = self.gcd(b, a % b)
		x = y1
		y = x1 - y1 * (a // b)
		return (gcd1, x, y)


class Solution:

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


class Solution:

	def gcd(self, a, b):
		(s0, s1) = (1, 0)
		(t0, t1) = (0, 1)
		while b != 0:
			(q, r) = divmod(a, b)
			(a, b) = (b, r)
			if r != 0:
				si = s0 - q * s1
				ti = t0 - q * t1
				(s0, s1) = (s1, si)
				(t0, t1) = (t1, ti)
		return (a, s1, t1)


class Solution:

	def gcd1(self, a, b, p, q):
		if b == 0:
			return [a, p]
		return self.gcd1(b, a % b, q, p - a // b * q)

	def gcd(self, a, b):
		k = self.gcd1(a, b, 1, 0)
		return [k[0], k[1], (k[0] - k[1] * a) // b]


from math import gcd

class Solution:

	def gcd(self, a, b):

		def f(a, b):
			if b == 0:
				return [1, 0]
			(x_, y_) = f(b, a % b)
			return [y_, x_ - a // b * y_]
		return (gcd(a, b), f(a, b)[0], f(a, b)[1])


class Solution:

	def gcd(self, a, b):
		(p1, q1, h1) = (1, 0, a)
		(p2, q2, h2) = (0, 1, b)
		while h2:
			r = h1 // h2
			p3 = p1 - r * p2
			q3 = q1 - r * q2
			h3 = h1 - r * h2
			(p1, q1, h1) = (p2, q2, h2)
			(p2, q2, h2) = (p3, q3, h3)
		return (h1, p1, q1)


class Solution:

	def gcd(self, a, b):
		if b == 0:
			return (a, 1, 0)
		(d, x1, y1) = self.gcd(b, a % b)
		return (d, y1, x1 - y1 * (a // b))


class Solution:

	def gcd(self, a, b):
		if b == 0:
			(gcd, s, t) = (a, 1, 0)
			return (gcd, s, t)
		else:
			(s2, t2, s1, t1) = (1, 0, 0, 1)
			while b > 0:
				q = a // b
				(r, s, t) = (a - b * q, s2 - q * s1, t2 - q * t1)
				(a, b, s2, t2, s1, t1) = (b, r, s1, t1, s, t)
			(gcd, s, t) = (a, s2, t2)
			return (gcd, s, t)


class Solution:

	def gcd(self, a, b):

		def gcdExtended(a, b):
			if a == 0:
				return (b, 0, 1)
			(gcd, x1, y1) = gcdExtended(b % a, a)
			x = y1 - b // a * x1
			y = x1
			return (gcd, x, y)
		(d, a, b) = gcdExtended(a, b)
		return (d, a, b)


class Solution:

	def gcd(self, a, b):

		def getxy(a, b, lis):
			if b == 0:
				lis[0] = 1
				lis[1] = 0
				return a
			gd = getxy(b, a % b, lis)
			x = lis[1]
			y = lis[0] - a // b * lis[1]
			lis[1] = y
			lis[0] = x
			return gd
		lis = [0, 0]
		gd = getxy(a, b, lis)
		return [gd, lis[0], lis[1]]


class Solution:

	def Extendedform(self, a, b, x, y):
		if a == 0:
			x = 0
			y = 1
			return (b, x, y)
		(gcd, x1, y1) = self.Extendedform(b % a, a, 0, 0)
		x = y1 - b // a * x1
		y = x1
		return (gcd, x, y)

	def gcd(self, a, b):
		return list(self.Extendedform(a, b, 0, 0))


class Solution:

	def gcd2(self, a, b, t11, t12, t21, t22):
		if b == 0:
			return (a, t21, t11)
		n = a // b
		r = a % b
		t1 = t11 - n * t12
		t2 = t21 - n * t22
		return self.gcd2(b, r, t12, t1, t22, t2)

	def gcd(self, a, b):
		return self.gcd2(a, b, 0, 1, 1, 0)


class Solution:

	def gcd(self, a, b):
		x = 1
		y = 0
		x1 = 0
		y1 = 1
		m1 = a
		n1 = b
		while n1:
			q = m1 // n1
			temp = x
			x = x1
			x1 = temp - q * x1
			temp = y
			y = y1
			y1 = temp - q * y1
			temp = m1
			m1 = n1
			n1 = temp - q * n1
		return [m1, x, y]


class Solution:

	def gcd(self, a, b):
		v = []
		if a == 0:
			v.append(b)
			v.append(0)
			v.append(1)
			return v
		r = self.gcd(b % a, a)
		v.append(r[0])
		v.append(r[2] - b // a * r[1])
		v.append(r[1])
		return v
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(a, b) = input().split()
		ob = Solution()
		v = ob.gcd(int(a), int(b))
		print(v[0], end=' ')
		print(v[1], end=' ')
		print(v[2])


class Solution:

	def gcd(self, a, b):
		if b == 0:
			return [a, 1, 0]
		solution = self.gcd(b, a % b)
		return [solution[0], solution[2], solution[1] - a // b * solution[2]]


class Solution:

	def gcd(self, a, b):
		(alpha, beta) = (a, b)
		(c1, c2) = (1, 0)
		(c3, c4) = (0, 1)
		while beta > 0:
			(t1, t2) = (c1, c2)
			(c1, c2) = (c3, c4)
			(c3, c4) = (t1 - alpha // beta * c3, t2 - alpha // beta * c4)
			(alpha, beta) = (beta, alpha % beta)
		return (alpha, c1, c2)


class Solution:

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


class Solution:

	def gcd(self, a, b):
		(x, y) = (1, 0)
		(x1, y1) = (0, 1)
		while b:
			q = a // b
			(x, y) = (y, x - q * y)
			(x1, y1) = (y1, x1 - q * y1)
			(a, b) = (b, a % b)
		return (a, x, x1)


class Solution:

	def gcd(self, a, b):
		if a >= b:
			pstate = {'r': a, 'q': 0, 'x': 1, 'y': 0}
			state = {'r': b, 'q': a // b, 'x': 0, 'y': 1}
		else:
			pstate = {'r': b, 'q': 0, 'x': 0, 'y': 1}
			state = {'r': a, 'q': b // a, 'x': 1, 'y': 0}
		nstate = {'r': 0, 'q': 0, 'x': 0, 'y': 0}
		while state['r'] != 0:
			nstate['r'] = pstate['r'] - state['q'] * state['r']
			nstate['q'] = state['r'] // pstate['r']
			nstate['x'] = pstate['x'] - state['q'] * state['x']
			nstate['y'] = pstate['y'] - state['q'] * state['y']
			(pstate, state) = (state, pstate)
			(state, nstate) = (nstate, state)
		return [pstate['r'], pstate['x'], pstate['y']]


class Solution:

	def gcd(self, a, b):

		def ExGcd(a, b):
			if a == 0:
				return (b, 0, 1)
			(GCD, x1, y1) = ExGcd(b % a, a)
			x = y1 - b // a * x1
			y = x1
			return (GCD, x, y)
		return ExGcd(a, b)


class Solution:

	def gcd(self, a, b):
		h = []
		if b == 0:
			h.append(a)
			h.append(1)
			h.append(0)
			return h
		d = self.gcd(b, a % b)
		h.append(d[0])
		h.append(d[2])
		h.append(d[1] - d[2] * (a // b))
		return h


class Solution:

	def gcd(self, a, b):
		v = []
		if a == 0:
			v.append(b)
			v.append(0)
			v.append(1)
			return v
		r = self.gcd(b % a, a)
		v.append(r[0])
		v.append(r[2] - b // a * r[1])
		v.append(r[1])
		return v