P10269 Strength Faction


There are $n$ OIers from all over the country who form a team called "实力派" (shílìpài). Each person has a strength value $a_i$. There are $m$ contests that send them invitations. In the $i$-th contest, they are required to form a team of $k_i$ people to participate. To decide whether they should join a contest, they came up with the following two measures of strength: - Define the $x$-th order minimum strength as the number of ways to choose $x$ people from these $n$ people such that the $\gcd=1$ of the chosen $x$ people's strength values; - Define the $x$-th order maximum strength as the sum of the $\gcd$ of the chosen $x$ people over all possible choices. For each contest, please tell them the $k_i$-th order minimum strength and maximum strength for that contest. Also, to keep others from understanding, you need to take the answers modulo a secret modulus $p$.

The first line contains three integers $n,m,p$, representing the number of team members, the number of contests, and the secret modulus, respectively. The second line contains $n$ integers. The $i$-th integer represents the strength value $a_i$ of the $i$-th person. The next $m$ lines each contain one integer $k_i$, meaning the required number of participants for the $i$-th contest.

Output $m$ lines. The $i$-th line contains two integers $min_i,max_i$, representing the minimum strength and maximum strength in the $i$-th contest, with answers taken modulo $p$.

**Sample** $\mathbf{1}$ **Explanation** In the first contest, they need to choose $2$ people. Only the choice $(8,15)$ has $\gcd=1$, so the minimum strength is $1$. The sum of $\gcd$ over all choices is $19$, so the maximum strength is $19$. In the second contest, they need to choose $3$ people. There are two choices with $\gcd=1$: $(8,15,12)$ and $(8,15,6)$. Therefore, the minimum strength is $2$. The sum of $\gcd$ over all choices is $7$, so the maximum strength is $7$. **Constraints** For all data, $1\leq n,m,k_i\leq 2\times 10^5$, $1\leq a_i\leq 10^6$, $10^7\leq p\leq 10^9$, and $p\in \mathbb{P}$. This problem has a total of $30$ test points and **uses bundled tests**. The subtasks and test point distribution are as follows: | Subtask ID | Test Point ID | Special Property | Score | Time Limit | | :-: | :-: | :-: | :-: | :-: | | $0$ | $1\sim 4$ | $n\leq 20$ | $10$ | $1s$ | | $1$ | $5\sim 8$ | $n,a_i\leq 300$ | $10$ | $1s$ | | $2$ | $9\sim 12$ | $k_i\leq 2$ | $20$ | $1.5s$ | | $3$ | $13\sim 16$ | $a_i\leq 3$ | $10$ | $1s$ | | $4$ | $17\sim 22$ | $a_i\leq 10^5$ | $20$ | $1s$ | | $5$ | $23\sim 30$ | No special property | $30$ | $1.5s$ | **Hint** $\mathbb{P}$ denotes the set of all prime numbers, and $\gcd$ denotes the greatest common divisor. Translated by ChatGPT 5