The Chinese Remainder Theorem tells us that we can always find a number that produces any required remainders under different prime moduli. Your goal is to write code to output such a number in polynomial time. Shortest code wins.
For example, say we're given these constraints (
% represents mod):
n % 7 == 2 n % 5 == 4 n % 11 == 0
One solution is
n=44. The first constraint is satisfied because
44 = 6*7 + 2, and so
44 has remainder
2 when divided by
7, and thus
44 % 7 == 2. The other two constraints are met as well. There exist other solutions, such as
A non-empty list of pairs
(p_i,a_i), where each modulus
p_i is a distinct prime and each target
a_i is a natural number in the range
0 <= a_i < p_i. You can take input in whatever form is convenient; it doesn't have to actually be a list of pairs. You may not assume the input is sorted.
n such that
n % p_i == a_i for each index
i. It doesn't have to be the smallest such value, and may be negative.
Polynomial time restriction
To prevent cheap solutions that just try
n=2, and so on, your code must run in polynomial time in the length of the input. Note that a number
m in the input has length
Θ(log m), so
m itself is not polynomial in its length. This means that you can't count up to
m or do an operation
m times, but you can compute arithmetic operations on the values.
You may not use an inefficient input format like unary to get around this.
Built-ins to do the following are not allowed: Implement the Chinese Remainder theorem, solve equations, or factor numbers.
You may use built-ins to find mods and do modular addition, subtraction, multiplication, and exponentiation (with natural-number exponent). You may not use other built-in modular operations, including modular inverse, division, and order-finding.
These give the smallest non-negative solution. Your answer may be different. It's probably better if you check directly that your output satisfies each constraint.
[(5, 3)] 3 [(7, 2), (5, 4), (11, 0)] 44 [(5, 1), (73, 4), (59, 30), (701, 53), (139, 112)] 1770977011 [(982451653, 778102454), (452930477, 133039003)] 68121500720666070