Function crt 

pub fn crt(r: &[i64], m: &[i64]) -> (i64, i64)

Performs CRT (Chinese Remainder Theorem).

Given two sequences $r, m$ of length $n$, this function solves the modular equation system

\[ x \equiv r_i \pmod{m_i}, \forall i \in \{0, 1, \cdots, n - 1\} \]

If there is no solution, it returns $(0, 0)$.

Otherwise, all of the solutions can be written as the form $x \equiv y \pmod z$, using integer $y, z\ (0 \leq y < z = \text{lcm}(m))$. It returns this $(y, z)$.

If $n = 0$, it returns $(0, 1)$.

Constraints

• $|r| = |m|$
• $1 \leq m_{\forall i}$
• $\text{lcm}(m)$ is in i64

Panics

Panics if the above constraints are not satisfied.

Complexity

• $O(n \log \text{lcm}(m))$

Example

use ac_library::math;

let r = [2, 3, 2];
let m = [3, 5, 7];
assert_eq!(math::crt(&r, &m), (23, 105));