4 /*Computes the solution to a system of simple linear congruences via the
5 Chinese Remainder Theorem.
6 This function solves the system of equations
8 A value x satisfies this equation if there exists an integer k such that
10 Note that under this definition, negative moduli are equivalent to positive
11 moduli, and a modulus of 0 demands exact equality.
12 x: Returns the solution, if it exists.
13 Otherwise, the value is unchanged.
14 a: An array of the a_i's.
15 m: An array of the m_i's.
16 These do not have to be relatively prime.
17 n: The number of equations in the system.
18 Return: -1 if the system is not consistent, otherwise the modulus by which
19 the solution is unique.
20 This modulus is the LCM of the m_i's, except in the case where one of
21 them is 0, in which case the return value is also 0.*/
22 int crt(int *_x,const int _a[],const int _m[],int _n);