git.ozlabs.org Git - ccan/blob - tterribe@email.unc.edu-nmbrthry/crt.h

   1 #if !defined(_crt_H)
   2 # define _crt_H (1)
   3
   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
   7    x = a_i (mod m_i)
   8   A value x satisfies this equation if there exists an integer k such that
   9    x = a_i + k*m_i
  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);
  23
  24 #endif