
'''simple docstring'''


from __future__ import annotations
def 				__magic_name__(					UpperCAmelCase__   :					int       ,							UpperCAmelCase__   :					int       ,							UpperCAmelCase__   :					int  ):
						assert n > 1 and a > 0 and greatest_common_divisor(UpperCAmelCase__       ,							UpperCAmelCase__  ) == 1
						((UpperCamelCase_)    ,(UpperCamelCase_)    ,(UpperCamelCase_))    :  Union[str, Any]				    =    extended_gcd(UpperCAmelCase__       ,							UpperCAmelCase__  )  # Implemented below
						UpperCamelCase_    :  Tuple				    =    (b * s) % n
						return x
def 				__magic_name__(					UpperCAmelCase__   :					int       ,							UpperCAmelCase__   :					int  ):
						((UpperCamelCase_)    ,(UpperCamelCase_))    :  Dict				    =    extended_euclid(UpperCAmelCase__       ,							UpperCAmelCase__  )  # Implemented below
						if b < 0:
												UpperCamelCase_    :  str				    =    (b % n + n) % n
						return b
def 				__magic_name__(					UpperCAmelCase__   :					int       ,							UpperCAmelCase__   :					int       ,							UpperCAmelCase__   :					int  ):
						UpperCamelCase_    :  Optional[int]				    =    invert_modulo(UpperCAmelCase__       ,							UpperCAmelCase__  )
						UpperCamelCase_    :  Optional[int]				    =    (b * s) % n
						return x
def 				__magic_name__(					UpperCAmelCase__   :					int       ,							UpperCAmelCase__   :					int  ):
						assert a >= 0 and b >= 0

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

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

						return (d, x, y)
def 				__magic_name__(					UpperCAmelCase__   :					int       ,							UpperCAmelCase__   :					int  ):
						if b == 0:
												return (1, 0)
						((UpperCamelCase_)    ,(UpperCamelCase_))    :  str				    =    extended_euclid(UpperCAmelCase__       ,							a % b  )
						UpperCamelCase_    :  Dict				    =    a // b
						return (y, x - k * y)
def 				__magic_name__(					UpperCAmelCase__   :					int       ,							UpperCAmelCase__   :					int  ):
						if a < b:
												UpperCamelCase_    ,UpperCamelCase_    :  str				    =    b, a

						while a % b != 0:
												UpperCamelCase_    ,UpperCamelCase_    :  Optional[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 .hash_table import HashTable
from .number_theory.prime_numbers import is_prime, next_prime




class 						__snake_case (						_a  ):




		def __init__(     self				:Optional[Any] ,						*_SCREAMING_SNAKE_CASE				:Union[str, Any] ,						**_SCREAMING_SNAKE_CASE				:List[Any])				-> List[str]:






								'''simple docstring'''






								super().__init__(*_SCREAMING_SNAKE_CASE ,						**_SCREAMING_SNAKE_CASE)




		def   _snake_case  (     self				:Union[str, Any] ,						_SCREAMING_SNAKE_CASE				:Union[str, Any] ,						_SCREAMING_SNAKE_CASE				:List[Any])				-> Optional[int]:






								'''simple docstring'''






								UpperCamelCase_    :  Optional[Any]				    =    (
								    next_prime(value % self.size_table)
								    if not is_prime(value % self.size_table)
								    else value % self.size_table
								)  # gt = bigger than
								return next_prime_gt - (data % next_prime_gt)




		def   _snake_case  (     self				:List[str] ,						_SCREAMING_SNAKE_CASE				:Optional[int] ,						_SCREAMING_SNAKE_CASE				:Any ,						_SCREAMING_SNAKE_CASE				:int)				-> Dict:






								'''simple docstring'''






								return (increment * self.__hash_function_a(_SCREAMING_SNAKE_CASE ,						_SCREAMING_SNAKE_CASE)) % self.size_table





		def   _snake_case  (     self				:Tuple ,						_SCREAMING_SNAKE_CASE				:Any ,						_SCREAMING_SNAKE_CASE				:int=None)				-> List[Any]:






								'''simple docstring'''






								UpperCamelCase_    :  Optional[Any]				    =    1
								UpperCamelCase_    :  str				    =    self.hash_function(_SCREAMING_SNAKE_CASE)

								while self.values[new_key] is not None and self.values[new_key] != key:
														UpperCamelCase_    :  int				    =    (
														    self.__hash_double_function(_SCREAMING_SNAKE_CASE ,						_SCREAMING_SNAKE_CASE ,						_SCREAMING_SNAKE_CASE)
														    if self.balanced_factor() >= self.lim_charge
														    else None
														)
														if new_key is None:
																				break
														else:
																				i += 1

								return new_key




