



"""simple docstring"""






from __future__ import annotations

import numpy as np






def      snake_case__   (		__lowerCamelCase				:    np.ndarray	):
			"""simple docstring"""
			lowerCamelCase__	,   lowerCamelCase__		:		Tuple			=np.shape(__lowerCamelCase	)
			if rows != columns:
						lowerCamelCase__		:		str			=(
						    '''\'table\' has to be of square shaped array but got a '''
						    f'''{rows}x{columns} array:\n{table}'''
						)
						raise ValueError(__lowerCamelCase	)

			lowerCamelCase__		:		Union[str, Any]			=np.zeros((rows, columns)	)
			lowerCamelCase__		:		Optional[int]			=np.zeros((rows, columns)	)
			for i in range(__lowerCamelCase	):
						for j in range(__lowerCamelCase	):
									lowerCamelCase__		:		List[Any]			=sum(lower[i][k] * upper[k][j] for k in range(__lowerCamelCase	)	)
									if upper[j][j] == 0:
												raise ArithmeticError('''No LU decomposition exists'''	)
									lowerCamelCase__		:		Optional[int]			=(table[i][j] - total) / upper[j][j]
						lowerCamelCase__		:		Any			=1
						for j in range(__lowerCamelCase							,		__lowerCamelCase	):
									lowerCamelCase__		:		str			=sum(lower[i][k] * upper[k][j] for k in range(__lowerCamelCase	)	)
									lowerCamelCase__		:		Union[str, Any]			=table[i][j] - total
			return lower, upper


if __name__ == "__main__":
		import doctest

		doctest.testmod()









"""simple docstring"""






from __future__ import annotations






def      snake_case__   (		__lowerCamelCase				:    int							,		__lowerCamelCase				:    int	):
			"""simple docstring"""
			if b == 0:
						return (1, 0)
			((lowerCamelCase__)	,   (lowerCamelCase__))		:		Any			=extended_euclid(__lowerCamelCase							,		a % b	)
			lowerCamelCase__		:		Optional[Any]			=a // b
			return (y, x - k * y)






def      snake_case__   (		__lowerCamelCase				:    int							,		__lowerCamelCase				:    int							,		__lowerCamelCase				:    int							,		__lowerCamelCase				:    int	):
			"""simple docstring"""
			((lowerCamelCase__)	,   (lowerCamelCase__))		:		Any			=extended_euclid(__lowerCamelCase							,		__lowerCamelCase	)
			lowerCamelCase__		:		List[Any]			=na * na
			lowerCamelCase__		:		Union[str, Any]			=ra * x * na + ra * y * na
			return (n % m + m) % m






def      snake_case__   (		__lowerCamelCase				:    int							,		__lowerCamelCase				:    int	):
			"""simple docstring"""
			((lowerCamelCase__)	,   (lowerCamelCase__))		:		int			=extended_euclid(__lowerCamelCase							,		__lowerCamelCase	)
			if b < 0:
						lowerCamelCase__		:		Any			=(b % n + n) % n
			return b






def      snake_case__   (		__lowerCamelCase				:    int							,		__lowerCamelCase				:    int							,		__lowerCamelCase				:    int							,		__lowerCamelCase				:    int	):
			"""simple docstring"""
			lowerCamelCase__	,   lowerCamelCase__		:		Any			=invert_modulo(__lowerCamelCase							,		__lowerCamelCase	), invert_modulo(__lowerCamelCase							,		__lowerCamelCase	)
			lowerCamelCase__		:		Tuple			=na * na
			lowerCamelCase__		:		Optional[Any]			=ra * x * na + ra * y * na
			return (n % m + m) % m


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

		testmod(name="chinese_remainder_theorem", verbose=True)
		testmod(name="chinese_remainder_theorem2", verbose=True)
		testmod(name="invert_modulo", verbose=True)
		testmod(name="extended_euclid", verbose=True)




