### Hi codeforces.

Today i meet the problem that calculate:

and `n <= 1e7`

and have `1e6`

testcase with `n`

with $$$t_{i}$$$ is divisor of n and $$$\phi{(t_{i})}$$$ is euler totient function. Help me to make it fast and can run 1s on codeforces. Thanks for your help.

same problem on codechef

https://www.codechef.com/problems/SMPLSUM

Maybe I can provide a very very slow solution.

Consider define $$$f_i=i \times \varphi(i)$$$ . We only need to calculate $$$\sum_{d|n} f(d)$$$ .

It can be considered as high dimension prefix sum.

You just need to store every prime number ( in a vector ) and do this :

Maybe it can run 1s on CF.

However it's not $$$O(n)$$$ .

I finally understand nor's solution. If $$$\gcd(a,b)=1$$$ , it's obvious that for all $$$d|ab$$$ , there is exactly one way to make $$$d=xy$$$ , when $$$x|a$$$ and $$$y|b$$$ .

So if $$$f(x)$$$ is multiplicative , $$$\sum_{d|x} f(d)$$$ is also multiplicative ! How smart it is !

Your solution is still quite close to linear, since the complexity (ignoring computing the list of primes) is $$$O\left(\sum_{\text{prime } p \le N} 1 + \left\lfloor\frac{N}{p}\right\rfloor\right) = O\left(\pi(N) + N \sum_{\text{prime } p \le N} \frac{1}{p}\right) = O(N \log \log N)$$$.

Note that $$$f(n) = n \phi(n)$$$ is a multiplicative function, so the answer to the problem, which is $$$g(n) = \sum_{d | n} f(d)$$$, is also multiplicative. It is easy to compute $$$g$$$ on prime powers as follows:

g(p^k) = \sum_{d | p^k} f(d) = 1 + \sum_{i = 1}^k p^i (p^i - p^{i - 1}) = \frac{p^{2k+1} + 1}{p + 1}

$$$

Using a linear sieve, this can be done using preprocessing in $$$O(N)$$$ and queries in $$$O(1)$$$.