VIRUSGAMING's blog

By VIRUSGAMING, history, 2 months ago,

Hi codeforces.

Today i meet the problem that calculate:

$\displaystyle\sum_{i=1}^{n}\frac{n}{gcd(i,n)}$

and n <= 1e7 and have 1e6 testcase with n

$\displaystyle\sum_{i=1}^{n}\frac{n}{gcd(i,n)} = \displaystyle\sum_{i=1}^{m}t_{i} * \phi{(t_{i})}$

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.

• +10

 » 2 months ago, # |   0 same problem on codechef
 » 2 months ago, # |   +8 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 : for(auto pr:vc) for(int i=1;i<=Mx/pr;i++) f[i*pr]+=f[i]; Maybe it can run 1s on CF.
•  » » 2 months ago, # ^ |   0 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 !
•  » » » 2 months ago, # ^ |   +1 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)$.
 » 2 months ago, # | ← Rev. 2 →   +27 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)$.