
ZOJ Problem Set  2612
Consider integer numbers in range from 0 to r1 for some r. They form a ring, denoted by Z_{r}. That means that you can perform addition, substraction and multiplication of the numbers, each time taking the result modulo r. Let us call some subset A {0, 1, ... , r1} stable with respect to a polynomial p(x) if A = {p(x)x A}. Note that the empty set is always stable with respect to any polynomial. Consider two polynomials Your task is to calculate the number of subsets of Z_{r} that are stable with repsect to both p(x) and q(x). Input The input contains one or more test cases. In each case, the first line contains r (2 <= r <= 100). Next line describes p(x), its degree n (0 <= n <= 100) is followed by n+1 integer numbers ranging from 0 to r1, they define a_{n}, a_{n1}, ... , a_{0}. Next line describes q(x) in a similar way. A constant zero polynomial has the degree of 0 for the purpose of this problem. A case with r = 0 ends up the input file, which should not be proceeded.
Output For each test case, output the only number  the number of subsets of Zr that are stable with repsect to both p(x) and q(x). Sample Input 6 1 2 0 1 1 2 0 Sample Output 2 Author: Andrew Stankevich Source: Andrew Stankevich's Contest #7 