P5881 [Chemistry] Experiment

Xiao Z sat nervously in front of a chemistry lab table, doing a chemistry experiment. A sigh came from the classroom again: I... I think I made a mistake again... Can I try one more time?

In front of her, there are $n$ test tubes. Each test tube contains an unknown liquid. For each kind of unknown liquid, there are $2$ known chemical attributes: $a$ and $b$. The two attribute values of the $i$-th liquid are $a_i$ and $b_i$. Now, the teacher assigns her $m$ experiments. For each experiment, there is a reference value $x$ (the reference value of the $i$-th experiment is denoted as $x_i$). She needs to divide the unknown liquids into as many groups as possible, such that: for any two liquids $i$ and $j$ in different groups, $\operatorname{gcsd(a_i,a_j)}$ must not be greater than $x^2$. Here, $\operatorname{gcsd}$ denotes the greatest common square divisor. $k$ is a common square divisor of two numbers if and only if it satisfies both of the following: - $k$ is a common divisor of the two numbers; - $k$ is a perfect square. The greatest common square divisor $\operatorname{gcsd}$ is the maximum $k$ among all $k$ that satisfy the conditions. Intuitively, $\operatorname{gcsd}$ can be understood as: take the greatest common divisor of the two numbers, take its square root, keep only the integer factor part, and then square it back. For example: To compute $\operatorname{gcsd(24,64)}$, first compute the greatest common divisor of $24$ and $64$, which is $8$. Then $\sqrt 8=2\sqrt 2$. Its integer factor is $2$, so $\operatorname{gcsd(24,64)}=2^2=4$. She also needs, under the condition that the number of groups is maximized, to maximize her experiment score. Definition of the experiment score: for each reagent, define its score $c_i$ as the largest **exponent** in the prime factorization of $b_i$. For example: $b_i=12=2^2\times 3^1$, so $c_i=\max\{2,1\}=2$. $b_i=90=2^1\times 3^2\times 5^1$, so $c_i=\max\{1,2,1\}=2$. The experiment score is the sum, over all groups, of the maximum $c_i$ within each group. Of course, her $IQ$ is not very high, so she needs to ask for your help.

The first line contains two integers $n,m$. The second line contains $n$ integers $a_{1\dots n}$. The third line contains $n$ integers $b_{1\dots n}$. The fourth line contains $m$ integers $x_{1\dots m}$.

Output $m$ lines. For the $i$-th line, output $2$ integers: the number of groups and the experiment score for the $i$-th experiment.

#### Sample Explanation #1 $b_1=2=2^1,c_1=1$. $b_2=4=2^2,c_2=2$. $b_3=6=2^1\times 3^1,c_3=\max\{1,1\}=1$. $b_4=8=2^3,c_4=3$. $b_5=10=2^1\times 5^1,c_5=\max\{1,1\}=1$. When $x=2$, it can be divided into three groups: $\{1,2,4\},\{3\},\{5\}$. The experiment score is $\max\{1,2,3\}+\max\{1\}+\max\{1\}=5$. ---------- #### Constraints **"This problem uses bundled testdata."** | subtask | $n\le$ | $m\le$ | $a_i \le$ | $b_i\le$ | $x \le$ | Score | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: |:-----------:| | $1$ | $4$ | $6$ | $100$ | $4 \times 10^4$ | $100$ | $5$ | | $2$ | $8$ | $7$ | $20$ | $10^3$ | $10$ | $5$ | | $3$ |$20$ | $30$ | $50$ | $8 \times 10^3$ | $100$ | $10$ | | $4$ |$100$ | $60$ | $100$ | $4 \times 10^4$ | $10^3$ | $10$ | | $5$ |$5 \times 10^3$ | $110$ | $10^3$| $10^5$ | $4 \times 10^3$ | $10$ | | $6$ |$2 \times 10^4$ | $250$ | $3 \times 10^3$ | $10^6$ | $3 \times 10^3$ | $10$ | | $7$ |$ 5 \times 10^4$| $10^3$ | $10^4$ | $2 \times 10^7$ | $1.5 \times 10^4$ | $15$ | | $8$ |$10^5$ | $8 \times 10^3$ | $2 \times 10^4$ | $2 \times 10^7$ | $2.2 \times 10^4$ | $15$ | | $9$ |$2 \times 10^5$ | $2 \times 10^5$ | $4 \times 10^4$ | $2 \times 10^7$ | $3 \times 10^4$ | $20$ | For $100\%$ of the data: $1 \le n,m \le 2\times 10^5$, $2 \le a_i \le 4\times 10^4$, $2 \le b_i \le 2\times 10^7$, $2 \le x \le 3\times 10^4$. I... I think I made a mistake again... Can I try one more time? Translated by ChatGPT 5