Need help in generalization of formula
Разница между en1 и en2, 47 символ(ов) изменены
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!

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский prudent 2018-06-21 17:15:45 47 Tiny change: 'which's $\ge x$ \n ' -> 'which's $\le x$ \n '
en1 Английский prudent 2018-06-20 14:25:09 722 Initial revision (published)