



'''simple docstring'''







from __future__ import annotations







def  SCREAMING_SNAKE_CASE__ (				SCREAMING_SNAKE_CASE ,		SCREAMING_SNAKE_CASE ,		SCREAMING_SNAKE_CASE     ):
		assert (
		    c % greatest_common_divisor(A__ ,		A__     ) == 0
		)  # greatest_common_divisor(a,b) function implemented below
		((SCREAMING_SNAKE_CASE_)						,		(SCREAMING_SNAKE_CASE_)						,		(SCREAMING_SNAKE_CASE_))						:Optional[Any]										=      extended_gcd(A__ ,		A__     )  # extended_gcd(a,b) function implemented below
		SCREAMING_SNAKE_CASE_						:Union[str, Any]										=      c / d
		return (r * x, r * y)







def  SCREAMING_SNAKE_CASE__ (				SCREAMING_SNAKE_CASE ,		SCREAMING_SNAKE_CASE ,		SCREAMING_SNAKE_CASE ,		SCREAMING_SNAKE_CASE = 2     ):
		((SCREAMING_SNAKE_CASE_)						,		(SCREAMING_SNAKE_CASE_))						:Any										=      diophantine(A__ ,		A__ ,		A__     )  # Initial value
		SCREAMING_SNAKE_CASE_						:List[Any]										=      greatest_common_divisor(A__ ,		A__     )
		SCREAMING_SNAKE_CASE_						:List[Any]										=      a // d
		SCREAMING_SNAKE_CASE_						:Tuple										=      b // d

		for i in range(A__     ):
				SCREAMING_SNAKE_CASE_						:List[Any]										=      xa + i * q
				SCREAMING_SNAKE_CASE_						:str										=      ya - i * p
				print(A__ ,		A__     )







def  SCREAMING_SNAKE_CASE__ (				SCREAMING_SNAKE_CASE ,		SCREAMING_SNAKE_CASE     ):
		if a < b:
				SCREAMING_SNAKE_CASE_						,		SCREAMING_SNAKE_CASE_						:Union[str, Any]										=      b, a

		while a % b != 0:
				SCREAMING_SNAKE_CASE_						,		SCREAMING_SNAKE_CASE_						:Any										=      b, a % b

		return b







def  SCREAMING_SNAKE_CASE__ (				SCREAMING_SNAKE_CASE ,		SCREAMING_SNAKE_CASE     ):
		assert a >= 0 and b >= 0

		if b == 0:
				SCREAMING_SNAKE_CASE_						,		SCREAMING_SNAKE_CASE_						,		SCREAMING_SNAKE_CASE_						:Optional[Any]										=      a, 1, 0
		else:
				((SCREAMING_SNAKE_CASE_)						,		(SCREAMING_SNAKE_CASE_)						,		(SCREAMING_SNAKE_CASE_))						:Union[str, Any]										=      extended_gcd(A__ ,		a % b     )
				SCREAMING_SNAKE_CASE_						:List[str]										=      q
				SCREAMING_SNAKE_CASE_						:List[str]										=      p - q * (a // b)

		assert a % d == 0 and b % d == 0
		assert d == a * x + b * y

		return (d, x, y)


if __name__ == "__main__":
							from doctest import testmod

							testmod(name="""diophantine""", verbose=True)
							testmod(name="""diophantine_all_soln""", verbose=True)
							testmod(name="""extended_gcd""", verbose=True)
							testmod(name="""greatest_common_divisor""", verbose=True)



"""simple docstring"""




import numpy as np
from numpy import floataa
from numpy.typing import NDArray



def 						UpperCAmelCase__ (					A__						,     A__ )   ->   NDArray[floataa]:




   """simple docstring"""
   lowerCamelCase__       ,							lowerCamelCase__						       =      np.shape(A__ )

   lowerCamelCase__						       =      np.zeros((rows, 1)						,     dtype=A__ )
   for row in reversed(range(A__ ) ):
      lowerCamelCase__						       =      0
      for col in range(row + 1						,     A__ ):
         total += coefficients[row, col] * x[col]

      lowerCamelCase__						       =      (vector[row] - total) / coefficients[row, row]

   return x



def 						UpperCAmelCase__ (					A__						,     A__ )   ->   NDArray[floataa]:




   """simple docstring"""
   lowerCamelCase__       ,							lowerCamelCase__						       =      np.shape(A__ )
   if rows != columns:
      return np.array(()						,     dtype=A__ )

   # augmented matrix
   lowerCamelCase__						       =      np.concatenate((coefficients, vector)						,     axis=1 )
   lowerCamelCase__						       =      augmented_mat.astype("float64" )

   # scale the matrix leaving it triangular
   for row in range(rows - 1 ):
      lowerCamelCase__						       =      augmented_mat[row, row]
      for col in range(row + 1						,     A__ ):
         lowerCamelCase__						       =      augmented_mat[col, row] / pivot
         augmented_mat[col, :] -= factor * augmented_mat[row, :]

   lowerCamelCase__						       =      retroactive_resolution(
       augmented_mat[:, 0:columns]						,     augmented_mat[:, columns : columns + 1] )

   return x


if __name__ == "__main__":
     import doctest

     doctest.testmod()




