# N linear_congruences
# I {"version": "2.2", "import": ["math"], "abc": ["Iterable"]}
def linear_congruences(a_vals: Iterable[int],
m_vals: Iterable[int],
*,
coprime_moduli: bool = False) -> tuple[int, int]:
"""Returns a solution of the given system of linear congruences.
This function finds the smallest non-negative integer x0 and m, where any
x_k = x0 + k*m satisfies following simultaneous linear congruence equations:
x % m_0 = a_0
x % m_1 = a_1
...
x % m_n = a_n
The argument 'coprime_moduli' should be set True if all m_i's are pairwise
coprime. It runs faster by using Chinese Remainder Theorem.
"""
if coprime_moduli:
m_list = list(m_vals)
m = 1
for m_i in m_list:
m *= m_i
a = sum((p := m // m_i) * pow(p, -1, m_i) * a_i
for a_i, m_i in zip(a_vals, m_list)) % m
else:
a, m = 0, 1
for b, n in zip(a_vals, m_vals):
g = math.gcd(m, n)
l, mod = divmod(a - b, g)
if mod:
raise ValueError('No solution')
um = pow(m // g, -1, n // g) * m
m *= n // g
a = (a - l * um) % m
return a, m
# N prime_list
# I {"version": "1.3", "import": ["math"]}
def prime_list(a: int, b: int = -1) -> list[int]:
"""Returns a list of prime numbers in the given range, [1, a] or [a, b]."""
beg, end = (1, a + 1) if b < 0 else (min(a, b), max(a, b) + 1)
if end < 5:
return [i for i in range(beg, end) if i in (2, 3)]
n = end + 6 - end % 6
sieve = [False] + [True] * (n // 3 - 1)
for i in range(math.isqrt(n) // 3 + 1):
if sieve[i]:
d, s, j = (k := 1 | 3 * i + 1) * 2, k * k, k * (k + 4 - 2 * (i & 1))
sieve[s // 3::d] = [False] * ((n // 6 - s // 6 - 1) // k + 1)
sieve[j // 3::d] = [False] * ((n // 6 - j // 6 - 1) // k + 1)
b, e = (beg | 1) // 3, n // 3 - 2 + (end % 6 > 1)
return ([p for p in (2, 3) if p >= beg] +
[1 | 3 * i + 1 for i in range(b, e) if sieve[i]])