





from __future__ import annotations

import sys
def 				__UpperCamelCase  (		snake_case    ,	snake_case     )  ->						tuple[int, int]:


			'''simple docstring'''







			if abs(snake_case     ) == 1:
						return a, 0
			elif abs(snake_case     ) == 1:
						return 0, b

			__A ,						__A				 =       a, b
			__A ,						__A				 =       1, 0
			__A ,						__A				 =       0, 1

			while remainder != 0:
						__A				 =       old_remainder // remainder
						__A ,						__A				 =       remainder, old_remainder - quotient * remainder
						__A ,						__A				 =       coeff_a, old_coeff_a - quotient * coeff_a
						__A ,						__A				 =       coeff_b, old_coeff_b - quotient * coeff_b

			# sign correction for negative numbers
			if a < 0:
						__A				 =       -old_coeff_a
			if b < 0:
						__A				 =       -old_coeff_b

			return old_coeff_a, old_coeff_b
def 				__UpperCamelCase  (		)  ->						Tuple:


			'''simple docstring'''







			if len(sys.argv     ) < 3:
						print('''2 integer arguments required'''     )
						return 1
			__A				 =       int(sys.argv[1]     )
			__A				 =       int(sys.argv[2]     )
			print(extended_euclidean_algorithm(snake_case    ,	snake_case     )     )
			return 0


if __name__ == "__main__":
				raise SystemExit(main())








import numpy as np
def 				__UpperCamelCase  (		snake_case     )  ->						Any:


   '''simple docstring'''







   __A ,						__A				 =       a.shape
   __A				 =       min(snake_case    ,	snake_case     )
   __A				 =       np.eye(snake_case     )
   __A				 =       a.copy()

   for k in range(t - 1     ):
      # select a column of modified matrix A':
      __A				 =       r[k:, [k]]
      # construct first basis vector
      __A				 =       np.zeros_like(snake_case     )
      __A				 =       1.0
      # determine scaling factor
      __A				 =       np.linalg.norm(snake_case     )
      # construct vector v for Householder reflection
      __A				 =       x + np.sign(x[0]     ) * alpha * ea
      v /= np.linalg.norm(snake_case     )

      # construct the Householder matrix
      __A				 =       np.eye(m - k     ) - 2.0 * v @ v.T
      # pad with ones and zeros as necessary
      __A				 =       np.block([[np.eye(snake_case     ), np.zeros((k, m - k)     )], [np.zeros((m - k, k)     ), q_k]]     )

      __A				 =       q @ q_k.T
      __A				 =       q_k @ r

   return q, r


if __name__ == "__main__":
    import doctest

    doctest.testmod()

