P3768 A Simple Math Problem

Since the problem setter is too lazy to write a background, let's keep the problem simple. Given two integers $p$ and $n$, compute: $$\left(\sum_{i=1}^n\sum_{j=1}^n ij \gcd(i,j)\right) \bmod p$$ Here $\gcd(a,b)$ denotes the greatest common divisor of $a$ and $b$.

A single line containing two integers $p$ and $n$.

Output a single integer on one line, the answer.

For 20% of the testdata, $n \leq 1000$. For 30% of the testdata, $n \leq 5000$. For 60% of the testdata, $n \leq 10^6$, time limit 1 s. For another 20% of the testdata, $n \leq 10^9$, time limit 3 s. For the last 20% of the testdata, $n \leq 10^{10}$, time limit 4 s. For 100% of the testdata, $5 \times 10^8 \leq p \leq 1.1 \times 10^9$ and $p$ is prime. Translated by ChatGPT 5