



from __future__ import annotations


def 			snake_case_					( _lowerCAmelCase  :						List[str]       ,				_lowerCAmelCase  :						Tuple       ,				_lowerCAmelCase  :						Union[str, Any]  )				->       Tuple:
							assert n > 1 and a > 0 and greatest_common_divisor(_UpperCAmelCase       ,				_UpperCAmelCase  ) == 1
							(UpperCAmelCase)			:	Tuple										=		extended_gcd(_UpperCAmelCase       ,				_UpperCAmelCase  )  # Implemented below
							UpperCAmelCase			:	Tuple										=		(b * s) % n
							return x


def 			snake_case_					( _lowerCAmelCase  :						int       ,				_lowerCAmelCase  :						int  )				->       Optional[int]:
							(UpperCAmelCase)			:	List[str]										=		extended_euclid(_UpperCAmelCase       ,				_UpperCAmelCase  )  # Implemented below
							if b < 0:
														UpperCAmelCase			:	Any										=		(b % n + n) % n
							return b


def 			snake_case_					( _lowerCAmelCase  :						List[str]       ,				_lowerCAmelCase  :						Union[str, Any]       ,				_lowerCAmelCase  :						List[str]  )				->       Optional[int]:
							UpperCAmelCase			:	List[str]										=		invert_modulo(_UpperCAmelCase       ,				_UpperCAmelCase  )
							UpperCAmelCase			:	int										=		(b * s) % n
							return x


def 			snake_case_					( _lowerCAmelCase  :						Optional[int]       ,				_lowerCAmelCase  :						Union[str, Any]  )				->       Optional[Any]:
							assert a >= 0 and b >= 0

							if b == 0:
														UpperCAmelCase			:	Any										=		a, 1, 0
							else:
														(UpperCAmelCase)			:	Dict										=		extended_gcd(_UpperCAmelCase       ,				a % b  )
														UpperCAmelCase			:	int										=		q
														UpperCAmelCase			:	Any										=		p - q * (a // b)

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

							return (d, x, y)


def 			snake_case_					( _lowerCAmelCase  :						Union[str, Any]       ,				_lowerCAmelCase  :						List[Any]  )				->       List[str]:





							if b == 0:
														return (1, 0)
							(UpperCAmelCase)			:	Union[str, Any]										=		extended_euclid(_UpperCAmelCase       ,				a % b  )
							UpperCAmelCase			:	int										=		a // b
							return (y, x - k * y)


def 			snake_case_					( _lowerCAmelCase  :						Dict       ,				_lowerCAmelCase  :						Optional[Any]  )				->       Optional[int]:





							if a < b:
														UpperCAmelCase			:	Any										=		b, a

							while a % b != 0:
														UpperCAmelCase			:	int										=		b, a % b

							return b


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

						testmod(name="modular_division", verbose=True)
						testmod(name="modular_division2", verbose=True)
						testmod(name="invert_modulo", verbose=True)
						testmod(name="extended_gcd", verbose=True)
						testmod(name="extended_euclid", verbose=True)
						testmod(name="greatest_common_divisor", verbose=True)










'''simple docstring'''






from __future__ import annotations


def 			snake_case_					( _lowerCAmelCase  :						list[int]       ,				_lowerCAmelCase  :						int  )				->       list[int]:
							UpperCAmelCase			:	dict[int, int]										=		{}
							for index, val in enumerate(_lowerCAmelCase  ):
														UpperCAmelCase			:	Tuple										=		target - val
														if compl in chk_map:
																					return [chk_map[compl], index]
														UpperCAmelCase			:	Any										=		index
							return []


if __name__ == "__main__":
						import doctest

						doctest.testmod()
						print(F"{two_sum([2, 7, 11, 15], 9) = }")





