Keep Talking and Nobody Explodes Mod Chinese Remainder Theorem

On the Subject of CRT

yo phone linging

  1. Each screen has a modulo number and a remainder.
  2. Write down all modulus and all remainders.
  3. Compile arrays M (for modulus) and R (for remainders).
  4. Assign A=M[0], Z=R[0], i=1.
  5. Find x (in range (0..M[i]-1)), such that: (A*x+Z)%M[i] == R[i].
  6. Assign A=A*x+Z, Z=R[i], i=i+1.
  7. If i==M.length, submit A. Else return to step 2.

Notice: if lcd(M[0],...,M[i-1],M[i]) == lcd(M[0],...,M[i-1]), you can safely disregard screen with M[i].

Page 1 of 1