



"""simple docstring"""






from __future__ import annotations






def 	snake_case__  (						__lowerCamelCase							:       int				,						__lowerCamelCase							:       int				,						__lowerCamelCase							:       int      ):
			"""simple docstring"""
			assert (
			    c % greatest_common_divisor(__lowerCamelCase				,						__lowerCamelCase      ) == 0
			)  # greatest_common_divisor(a,b) function implemented below
			((lowerCamelCase__)      ,  (lowerCamelCase__)      ,  (lowerCamelCase__))						:						Any						      =extended_gcd(__lowerCamelCase				,						__lowerCamelCase      )  # extended_gcd(a,b) function implemented below
			lowerCamelCase__						:						Any						      =c / d
			return (r * x, r * y)






def 	snake_case__  (						__lowerCamelCase							:       int				,						__lowerCamelCase							:       int				,						__lowerCamelCase							:       int				,						__lowerCamelCase							:       int = 2      ):
			"""simple docstring"""
			((lowerCamelCase__)      ,  (lowerCamelCase__))						:						Tuple						      =diophantine(__lowerCamelCase				,						__lowerCamelCase				,						__lowerCamelCase      )  # Initial value
			lowerCamelCase__						:						Union[str, Any]						      =greatest_common_divisor(__lowerCamelCase				,						__lowerCamelCase      )
			lowerCamelCase__						:						Optional[int]						      =a // d
			lowerCamelCase__						:						Dict						      =b // d

			for i in range(__lowerCamelCase      ):
						lowerCamelCase__						:						Any						      =xa + i * q
						lowerCamelCase__						:						int						      =ya - i * p
						print(__lowerCamelCase				,						__lowerCamelCase      )






def 	snake_case__  (						__lowerCamelCase							:       int				,						__lowerCamelCase							:       int      ):
			"""simple docstring"""
			if a < b:
						lowerCamelCase__      ,  lowerCamelCase__						:						List[Any]						      =b, a

			while a % b != 0:
						lowerCamelCase__      ,  lowerCamelCase__						:						Optional[Any]						      =b, a % b

			return b






def 	snake_case__  (						__lowerCamelCase							:       int				,						__lowerCamelCase							:       int      ):
			"""simple docstring"""
			assert a >= 0 and b >= 0

			if b == 0:
						lowerCamelCase__      ,  lowerCamelCase__      ,  lowerCamelCase__						:						Optional[int]						      =a, 1, 0
			else:
						((lowerCamelCase__)      ,  (lowerCamelCase__)      ,  (lowerCamelCase__))						:						List[str]						      =extended_gcd(__lowerCamelCase				,						a % b      )
						lowerCamelCase__						:						int						      =q
						lowerCamelCase__						:						Optional[Any]						      =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)











from ..utils import DummyObject, requires_backends



class  SCREAMING_SNAKE_CASE_  ( metaclass=SCREAMING_SNAKE_CASE__			):


  """simple docstring"""





  _a								=							["""torch""", """transformers""", """k_diffusion"""]





  def __init__(  self	,  *A	,  **A						)		->   Optional[Any]:





       '''simple docstring'''







       requires_backends(self	,  ['''torch''', '''transformers''', '''k_diffusion''']						)





  @classmethod
  def 			__A      (  cls	,  *A	,  **A						)		->   Dict:





       '''simple docstring'''







       requires_backends(cls	,  ['''torch''', '''transformers''', '''k_diffusion''']						)







  @classmethod
  def 			__A      (  cls	,  *A	,  **A						)		->   Optional[Any]:





       '''simple docstring'''







       requires_backends(cls	,  ['''torch''', '''transformers''', '''k_diffusion''']						)