
ZOJ Problem Set  3562
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 m_{1}, m_{2}, ..., m_{k}. Then, Alice generates a sequence of integers naming a_{1}, a_{2}, ..., a_{k}, with this formula a_{i} = B mod m_{i}. 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). InputThere 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 m_{1}, m_{2}, ..., m_{k}. The third line of each case contains k integers, naming a_{1}, a_{2}, ..., a_{k} as description above. Then comes two integers l and r in one line. (0 ≤ l ≤ r < 2^{63}) Notice that all of integers in the input are nonnegative and would not exceed or equal 2^{63}. OutputFor 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 nonzero, 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. Sample Input4 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 Sample Output1 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 Contest: ZOJ Monthly, December 2011 