P10117 [LMXOI Round 1] Dreamer

[Enhanced version link](https://www.luogu.com.cn/problem/U402756)。 This is a math problem, but it was made by LMX for HQZ.

Define the multiplicative function $f(n)=(\mu \ast\operatorname{Id_2})(n)$. Given $n,k$, you need to compute $$\sum_{i_1\mid n}\sum_{i_2\mid i_1}\cdots\sum_{i_k\mid i_{k-1}}f(i_k)i_1i_k\mu^2\left(\dfrac{i_1}{i_k}\right)$$ #### Tips $\mu$ denotes the Möbius function. For $f$, we have $f(n)=\displaystyle \sum_{d\mid n}\mu(d)\left(\dfrac{n}{d}\right)^2$.

This problem has multiple test cases. The first line contains a positive integer $T$, the number of test cases. Since $n$ is very large, we will give the standard prime factorization of $n=\displaystyle \prod_{i=1}^t p_i^{\alpha_i}$. For each query, we first give two integers $k,m$. The second line contains $t$, and the next $t$ lines each contain two integers $p_i,\alpha_i$. (It is guaranteed that $p_i\ge p_{i-1}$ for $i\ge 2$, and $\alpha_i\ge 1$.)

For each query, output one line: the answer modulo $m$.

For $100\%$ of the testdata, $T \le 20,n\le 10^{24},1\le k\le 10^6,m\le 1.14\times 10^9$. | Test Point ID | $n$ | $k$ | $T$ | Special Property | | :-----------: | :-----------: | :--------: | :------: | :--------------: | | $1$ | $\le 80$ | $\le 4$ | $\le 5$ | $N$ | | $2$ | $\le 10^6$ | $\le 10$ | $\le 5$ | $N$ | | $3$ | $\le 10^{12}$ | $\le 20$ | $\le 20$ | $N$ | | $4$ | $\le 10^{18}$ | $\le 1$ | $\le 20$ | $N$ | | $5$ | $\le 10^{18}$ | $\le 10^3$ | $\le 20$ | $N$ | | $6$ | $\le 10^{18}$ | $\le 10^5$ | $\le 20$ | $A$ | | $7$ | $\le 10^{18}$ | $\le 10^6$ | $\le 20$ | $B$ | | $8$ | $\le 10^{24}$ | $\le 10^6$ | $\le 20$ | $B$ | | $9$ | $\le 10^{24}$ | $\le 10^6$ | $\le 20$ | $C$ | | $10\sim20$ | $\le 10^{24}$ | $\le 10^6$ | $\le 20$ | $N$ | Property $A$: It is guaranteed that $t\le 10$. Property $B$: In the prime factorization $\displaystyle\prod_{i=1}^t p_i^{\alpha_i}$ of $n$, $\alpha_i=1$. Property $C$: $m$ is prime, and it is guaranteed that $\gcd(n,m)=1$. Translated by ChatGPT 5