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.
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)$$$.