P6825 "EZEC-4" Summation

Given the value of a positive integer $n$, compute the value of the following expression: $$\displaystyle\sum_{i = 1}^n \sum_{j = 1}^n \gcd(i,j)^{i + j}$$ Since the result may be very large, you only need to output the value modulo $p$.

**This problem contains multiple test cases.** The first line contains an integer $T$, representing the number of test cases. For each test case: One line contains two positive integers $n, p$.

For each test case, output one line with a positive integer, representing the required value.

**This problem enables O2 optimization and bundled tests.** **To eliminate incorrect solutions, the Constraints are intentionally set larger. Please pay attention to the impact of constant factors on your program.** ### Sample Explanation #### Sample #1 For the first test case: $\operatorname{ans} = \gcd(1, 1)^2 + \gcd(1, 2)^3 + \gcd(2, 1)^3 + \gcd(2, 2)^4 = 1^2 + 1^3 + 1^3 + 2^4 = 3 + 16 = 19$. Therefore, the answer is $19 \bmod (10^9 + 7) = 19$. ### Constraints | Subtask | $\sum n$ | Score | Time Limit | | :------: | :------: | :------: | :------: | | $1$ | $1 \leq \sum n \leq 500$ | $10 \operatorname{pts}$ | $1.00 \operatorname{s}$ | | $2$ | $1 \leq \sum n \leq 5 \times 10^5$ | $40 \operatorname{pts}$ | $3.20 \operatorname{s}$ | | $3$ | No special constraints | $50 \operatorname{pts}$ | $6.00 \operatorname{s}$ | For $100\%$ of the testdata, $1 \leq \sum n \leq 1.5 \times 10^6$, $2 \leq p \leq 2^{31} - 1$ and $p$ is prime, $1 \leq T \leq 2$. Translated by ChatGPT 5