




'''simple docstring'''






from __future__ import annotations




def 		a_(			lowerCamelCase ,					lowerCamelCase ,					lowerCamelCase   )					->Optional[Any]:






       '''simple docstring'''




       assert (
           c % greatest_common_divisor(lowerCAmelCase__ ,					lowerCAmelCase__   ) == 0
       )  # greatest_common_divisor(a,b) function implemented below
       (lowercase)	:		int    =   extended_gcd(lowerCAmelCase__ ,					lowerCAmelCase__   )  # extended_gcd(a,b) function implemented below
       lowercase	:		Union[str, Any]    =   c / d
       return (r * x, r * y)




def 		a_(			lowerCamelCase ,					lowerCamelCase ,					lowerCamelCase ,					lowerCamelCase = 2   )					->str:






       '''simple docstring'''




       (lowercase)	:		List[str]    =   diophantine(lowerCAmelCase__ ,					lowerCAmelCase__ ,					lowerCAmelCase__   )  # Initial value
       lowercase	:		List[str]    =   greatest_common_divisor(lowerCAmelCase__ ,					lowerCAmelCase__   )
       lowercase	:		List[str]    =   a // d
       lowercase	:		Tuple    =   b // d

       for i in range(lowerCAmelCase__   ):
              lowercase	:		List[Any]    =   xa + i * q
              lowercase	:		Tuple    =   ya - i * p
              print(lowerCAmelCase__ ,					lowerCAmelCase__   )




def 		a_(			lowerCamelCase ,					lowerCamelCase   )					->Any:






       '''simple docstring'''




       if a < b:
              lowercase	:		List[str]    =   b, a

       while a % b != 0:
              lowercase	:		Optional[int]    =   b, a % b

       return b




def 		a_(			lowerCamelCase ,					lowerCamelCase   )					->str:






       '''simple docstring'''




       assert a >= 0 and b >= 0

       if b == 0:
              lowercase	:		List[str]    =   a, 1, 0
       else:
              (lowercase)	:		str    =   extended_gcd(lowerCAmelCase__ ,					a % b   )
              lowercase	:		Optional[Any]    =   q
              lowercase	:		Dict    =   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'''
from __future__ import annotations


def 	lowercase_						( lowerCAmelCase__						:	int      ,				lowerCAmelCase__						:	int      ,				lowerCAmelCase__						:	int			):

			"""simple docstring"""





			assert (
			    c % greatest_common_divisor(lowerCAmelCase__      ,				lowerCAmelCase__			) == 0
			)  # greatest_common_divisor(a,b) function implemented below
			((__UpperCAmelCase)					,	(__UpperCAmelCase)					,	(__UpperCAmelCase)) :   int    					=  extended_gcd(lowerCAmelCase__      ,				lowerCAmelCase__			)  # extended_gcd(a,b) function implemented below
			__UpperCAmelCase :   Union[str, Any]    					=  c / d
			return (r * x, r * y)


def 	lowercase_						( lowerCAmelCase__						:	int      ,				lowerCAmelCase__						:	int      ,				lowerCAmelCase__						:	int      ,				lowerCAmelCase__						:	int = 2			):

			"""simple docstring"""





			((__UpperCAmelCase)					,	(__UpperCAmelCase)) :   List[str]    					=  diophantine(lowerCAmelCase__      ,				lowerCAmelCase__      ,				lowerCAmelCase__			)  # Initial value
			__UpperCAmelCase :   List[str]    					=  greatest_common_divisor(lowerCAmelCase__      ,				lowerCAmelCase__			)
			__UpperCAmelCase :   List[str]    					=  a // d
			__UpperCAmelCase :   Tuple    					=  b // d

			for i in range(lowerCAmelCase__			):
						__UpperCAmelCase :   List[Any]    					=  xa + i * q
						__UpperCAmelCase :   Tuple    					=  ya - i * p
						print(lowerCAmelCase__      ,				lowerCAmelCase__			)


def 	lowercase_						( lowerCAmelCase__						:	int      ,				lowerCAmelCase__						:	int			):

			"""simple docstring"""





			if a < b:
						__UpperCAmelCase					,	__UpperCAmelCase :   List[str]    					=  b, a

			while a % b != 0:
						__UpperCAmelCase					,	__UpperCAmelCase :   Optional[int]    					=  b, a % b

			return b


def 	lowercase_						( lowerCAmelCase__						:	int      ,				lowerCAmelCase__						:	int			):

			"""simple docstring"""





			assert a >= 0 and b >= 0

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




