112 - ZOJ Monthly, December 2011 - B
As we all know that the computer calculates the result between two integers in a large range is much slower than to calculate the result between two integers in a small range. Alice has been working on the factorization of the big integer. However, this problem is so hard for her to solve. One day, she comes up with an idea about the representation of a big integer. For convenience, we call the big integer as B.
First of all, Alice selects k integers, naming m1, m2, ..., mk. Then, Alice generates a sequence of integers naming a1, a2, ..., ak, with this formula ai = B mod mi. The sequence of m and the sequence of a are called the representation of big number B. Although this way of representation seems to be useful in the calculation, her intuition tells herself that the sequence of m and a may not represent the integer B uniquely, there may be another integer C generates the same sequence of m and a as B does.
For that you are one of the cleverest programmers in the world, Alice turns to you to help her find out whether the sequence of a represents the big number B uniquely. She wishes that you can write a program to find out all of the integers which match the representation of sequence m and sequence a in a specific range from l to r, inclusively, ( [l,r] equally).
There are multiple cases.
The first line of each case contains an integer k, k can be up to 100.
The second line of each case contains k integers, naming m1, m2, ..., mk. We assure that the least common multiple of all integers of sequence will not exceed or equal 263.
The third line of each case contains k integers, naming a1, a2, ..., ak as description above.
Then comes two integers l and r in one line. (0 ≤ l ≤ r < 263)
Notice that all of integers in the input are non-negative and would not exceed or equal 263.
For each case, the output should contain two line.
The first line of the output contains one integer indicating the count of integer B in the range [l,r] which match the representation of sequence of m and a.
If the count of integer B is non-zero, the second line should contain some of the numbers (in increasing order) which match the condition above. For the count can be so large, if the count is larger than 100, you only need to output the first 100 numbers. If the count is 0, the output contains only one line but not the second line.
4 11 111 1111 11111 10 1 10 10000 1 1000000000 4 32 64 128 256 31 30 31 30 1 1000000000 3 10 20 30 11 19 29 1 1000000000 2 2 3 1 2 1 100
1 1000000000 0 0 16 5 11 17 23 29 35 41 47 53 59 65 71 77 83 89 95
HintCase 2 and Case 3 indicate that the sequence of m and a might not represent any integers.
Author: XU, Zhongwen