P4527 [CTSC2008] Olympic Lottery

With $90$ days left before the opening of the Beijing $2008$ Olympics, CTSC plans to hold a lottery for volunteers. As one of the volunteers, you are very excited about it. The CTSC committee introduces the rules. Suppose there are $p$ volunteers in total. At the beginning, each volunteer receives a distinct number from $0$ to $p-1$. In the center of the screen are the avatars of the five Fuwa (Beibei, Jingjing, Huanhuan, Yingying, Nini), blinking to welcome everyone. When the lottery starts, the staff presses the button next to the screen and waits for the screen to stop. At that moment, the Fuwa stop blinking. Of course, when the screen stops, some Fuwa may have their eyes open while others have them closed. If all Fuwa have their eyes closed, the staff presses the button again, repeating this until at least one Fuwa has eyes open. Then, the staff observes which Fuwa have their eyes open. The five Fuwa are labeled as follows: Beibei, Jingjing, Huanhuan, Yingying, Nini are labeled $2$, $3$, $4$, $5$, $6$ respectively (the staff think $0$ and $1$ are not good numbers). Lucky numbers are defined as follows: - If a Fuwa’s eyes are open, then his/her label is a lucky number. - If numbers $l_1$ and $l_2$ (possibly equal) are lucky numbers, then their product is also a lucky number. - All other numbers are not lucky. Let $L$ denote the set of all lucky numbers. For example, if Beibei and Jingjing have eyes open while Huanhuan, Yingying, and Nini have eyes closed, then $L=\{2,3,4,6,8,9,12,\dots\}$. Let $l(x)$ denote the $x$-th lucky number in ascending order. For example, in the above case, $l(1)=2$, $l(4)=6$, and so on. Next, the staff randomly generates two numbers; let the smaller one be $a$ and the larger one be $b$. Define the set $T_{a,b}$ by $$T_{a,b}=\{\,d \mid d\in L,\ l(a)\mid d,\ d\mid l(b)\,\}$$ (where $x\mid y$ means $x$ divides $y$). Define the characteristic value $f$ of a finite subset of natural numbers as follows: - The characteristic value of the empty set is $0$. - For a non-empty set $S$, let $d$ be the smallest element of $S$. Then $$f(S)=d+f(S\backslash d)+q\times d\times f(S\backslash d),$$ where $S\backslash d$ denotes the set obtained by removing the element $d$ from $S$, and $q$ is a given non-negative integer. After $a$ and $b$ are generated, the winner’s number is the remainder when $f(T_{a,b})$ is divided by $p$. The staff will generate many pairs $(a,b)$, thus producing multiple winners. However, the on-site program takes a long time to compute the winners. Eager to know the results, you decide to rewrite the computation program, and your eyes turn to the keyboard in front of you.

The first line contains five space-separated numbers, each either $0$ or $1$, indicating whether Beibei, Jingjing, Huanhuan, Yingying, and Nini have their eyes open. Here $0$ means closed and $1$ means open. The $5$ numbers cannot all be $0$. The second line contains two space-separated numbers $p$ and $q$. Here $p$ is the number of volunteers, and $q$ is as described above for computing the characteristic value of a set. The third line contains the number $n$, the number of generated pairs $(a,b)$. Each of the next $n$ lines contains two space-separated integers $a$ and $b$, representing one lottery draw.

Output $n$ lines, each containing one integer, the winner’s number for that draw. The order corresponds one-to-one with the $n$ pairs $(a,b)$ in the input. Of course, a person may win multiple times.

Sample explanation: Beibei and Yingying have their eyes open. Therefore, the first $15$ lucky numbers are $2,4,5,8,10,16,20,25,32,40,50,64,80,100,125$. $l(1)=2$, $l(10)=40$. The lucky numbers that are multiples of $2$ and divisors of $40$ are $2,4,8,10,20,40$. So $T_{1,10}=\{2,4,8,10,20,40\}$. The characteristic value of $T_{1,10}$ is computed as follows: $f(\emptyset)=0$ $f(\{40\})=40+0+2\times40\times0=40$ $f(\{20,40\})=20+40+2\times20\times40=1660$ $f(\{10,20,40\})=10+1660+2\times10\times1660=34870$ $f(\{8,10,20,40\})=8+34870+2\times8\times34870=592798$ $f(\{4,8,10,20,40\})=4+592798+2\times4\times592798=5335186$ $f(\{2,4,8,10,20,40\})=2+5335186+2\times2\times5335186=26675932$ Therefore, the winner’s number is the remainder of $26675932$ divided by $10001$, which is $3265$. Similarly, $T_{2,12}=\{4,8,16,32,64\}$, whose characteristic value is $21167932$, and its remainder modulo $10001$ is $5816$. Also, $T_{4,15}=\emptyset$. Constraints: - For $20\%$ of the testdata, $1 \le a \le b \le 1000$, $n \le 2000$. - For $60\%$ of the testdata, $p$ is prime. - For $100\%$ of the testdata, $1 \le a \le b \le 10^5$, $n \le 10^5$, $p, q \le 2\times 10^9$. Translated by ChatGPT 5