A celebrated theorem of Dirichlet states that for any two coprime numbers a and m, there are an infinite number of primes congruent to a modulo m. This is often called the theorem on "primes in arithmetic progressions." This problem will experimentally verify a slight variation on this theme: given not just one congruence condition, but a list of several, can you find some prime satisfying all of them? Your task is to take a list of congruence conditions and find the smallest prime number that satisfies them all.
The first line gives the number of test cases, T. T test cases follow. Each case begins with a single line with an integer C, the number of congruence conditions for that test case. This is followed by C lines of the form ai mi (two integers separated by a space), which describe the congruence conditions.
For each test case, output one line containg "Case #x: y", where x is the case number (starting from 1) and y is the smallest prime number p that is congruent to aimodmi for all i.
In a given test case, any two moduli mi will be relatively prime, and the number ai will be relatively prime to mi.
Small dataset: in each test case, there is guaranteed to be a solution less than 108. The product of all of the moduli mi will also not exceed 108. The number C of congruence conditions in each test case will be either one or two.
Large dataset: in each test case, there is guaranteed to be a solution less than 1018. The product of all of the moduli mi will also not exceed 1018.
| Input | Output |
|
5 1 1 4 1 10 11 1 9 16 2 1 4 1 5 3 1 2 4 5 20 21 |
Case #1: 5 Case #2: 43 Case #3: 41 Case #4: 41 Case #5: 419 |
How to read the output of this sample: 5 is the smallest prime that is 1 mod 4; 43 is the smallest prime that is 10 mod 11; 41 is the smallest prime that is 9 mod 16; 41 is also the smallest prime that is both 1 mod 4 and 1 mod 5; 419 is the smallest prime that is 1 mod 2, 4 mod 5, and 20 mod 21.
The small input can be solved with a fairly naive algorithm that simply marches through the prime numbers and checks the against the desired congruence conditions. I suggest that you implement a naive solution first, since that will be a benchmark for anything more sophisticated. You could use the Sieve of Eratosthenes to find primes, or you could implement a simple primality test.
To solve the large input, I suggest that you first study the proof of the Chinese Remainder Theorem and figure out how you can use it to ``join'' the congruence conditions one by one into a single condition. Second, implement the Miller-Rabin primality test to quickly identify primes.
For the large input, you'll need to use at least 64-bit integers. For example, in C++ this means using the "long long" type; in Java it is just called "long". If you code in Python, this is a non-issue (since integers are all dynamically sized). Whatever language you use, you should look up the maximum size of the integer data type that you're using, and make sure it's big enough.
NOTE: the original posted large input had a problem due to a bug in my input generation script. The new one should have fixed the issue. I'm extending the submission deadline for the large input only until midnight on Friday.