P5493 Prime Prefix Statistics

This is important prerequisite knowledge for the Zhouge sieve and the Min_25 sieve.

Let $S(n)$ be the sum of the $k$-th powers of all primes not exceeding $n$. Given $N$, compute the value of the following expression: $$\sum_{i=1}^{\lfloor\sqrt{N}\rfloor} i^2 S \!\left( \left\lfloor \frac{N}{i} \right\rfloor \right)$$ All results are taken modulo the given prime $p$.

One line contains three integers $N, k, p$, separated by spaces.

Output one integer on one line, representing the computed result.

**Sample explanation**: $S \!\left( \left\lfloor \frac{N}{1} \right\rfloor \right)\! = S(10) = 2^3 + 3^3 + 5^3 + 7^3 = 503$. $S \!\left( \left\lfloor \frac{N}{2} \right\rfloor \right)\! = S(5) = 2^3 + 3^3 + 5^3 = 160$. $S \!\left( \left\lfloor \frac{N}{3} \right\rfloor \right)\! = S(3) = 2^3 + 3^3 = 35$. $1^2 S \!\left( \left\lfloor \frac{N}{1} \right\rfloor \right)\! + 2^2 S \!\left( \left\lfloor \frac{N}{2} \right\rfloor \right)\! + 3^2 S \!\left( \left\lfloor \frac{N}{3} \right\rfloor \right)\! = 503 + 640 + 315 = 1458$. ## Constraints | Test Point ID | $N \le$ | $k \le$ | Time Limit | | :--: | :--: | :--: | :--: | | $1\sim 3$ | $10^6$ | $10$ | $1\texttt s$ | | $4\sim 7$ | $4\times {10}^{10}$ | $0$ | $3\texttt s$ | | $8\sim 12$ | $4\times {10}^{10}$ | $10$ | $3\texttt s$ | For $100\%$ of the testdata, $0 \le k \le 10$, $1 \le N \le 4\times {10}^{10}$, ${10}^9 < p < 1.01 \times {10}^9$. Translated by ChatGPT 5