Problem was solved!↵
====================↵
↵
Input is consist of $1 \le q \le 2 * 10^4$ queries every of which are described with single positive integer $n$ not exceeding $4 * 10^6$. ↵
Output is to print for each query: $\sum\limits_{d = 1}^nP_{\lfloor{n/d}\rfloor}$ ↵
**Where:** ↵
$P_i = \sum\limits_{j = 2}^i\phi(j)$ ↵
$\lfloorx\rfloor =$ whole part of number, i.e. max integer which's $\gle x$ ↵
$\phi(x)$ is Euler Totient Function ↵
↵
OK, I can previously calculate phis of all numbers from $1$ to $4 * 10^6$ and $P_i$ for any $i$, $1 \le i \le 4 * 10^6$ in $O(n log n)$, but what's then? I don't know how to further optimize solution, because it is TLE with $O(n)$ complexity per query. ↵
Please, help me!
====================↵
↵
Input is consist of $1 \le q \le 2 * 10^4$ queries every of which are described with single positive integer $n$ not exceeding $4 * 10^6$. ↵
Output is to print for each query: $\sum\limits_{d = 1}^nP_{\lfloor{n/d}\rfloor}$ ↵
**Where:** ↵
$P_i = \sum\limits_{j = 2}^i\phi(j)$ ↵
$\lfloorx\rfloor =$ whole part of number, i.e. max integer which's $\
$\phi(x)$ is Euler Totient Function ↵
↵
OK, I can previously calculate phis of all numbers from $1$ to $4 * 10^6$ and $P_i$ for any $i$, $1 \le i \le 4 * 10^6$ in $O(n log n)$, but what's then? I don't know how to further optimize solution, because it is TLE with $O(n)$ complexity per query. ↵
Please, help me!
