proveus's blog

Number theory
By proveus, history, 21 month(s) ago, In English

Hi guys. Today i meet the problem that calculate sum of (n / gcd(i,n)) with i = 1,...,n and n <= 1e7 and have 1e6 testcase with n. I can find sum of (n / gcd(i,n)) = sum of (t * phi(t)) with t is divisor of n and phi(t) is euler totient function. Help me to make it fast and can run 1s on codeforces. Thanks for your help.

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

»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Let $$$f(n)$$$ be the answer for $$$n$$$. One can easily show that $$$f(n)$$$ is multiplicative. For $$$f(p^k)$$$, the answer is $$$1\times1+p\times(p-1)+p^2\times(p^2-p)+\cdots+p^k\times(p^k-p^{k-1})=1-p+p^2-p^3+p^4-\cdots+p^{2k}=\dfrac{p^{2k+1}+1}{p+1}$$$. One can use Euler sieve to pre-calculate the answer for every $$$n\le10^7$$$ in linear time. The complexity is linear to the maximum $$$n$$$ plus the number of testcases.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    When i use this,in case p is prime > 1e6 , i think it will be > long long type,what should i do :(

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Solution 1: Use __int128 in C++.

      Solution 2: when $$$k=1$$$, you can just use the brute force formula.(that is $$$p^2-p+1$$$)

      → Reply