VIRUSGAMING's blog

Small number theory technician
By VIRUSGAMING, history, 14 months ago, In English

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.

  • Vote: I like it
  • +10
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
14 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 !

    → Reply
    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

      → Reply
»
14 months ago, # |
← Rev. 2   Vote: I like it +27 Vote: I do not like it

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

→ Reply