proveus's blog

By proveus, history, 13 months 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

»
13 months 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

Unable to parse markup [type=CF_MATHJAX]

. One can use Euler sieve to pre-calculate the answer for every

Unable to parse markup [type=CF_MATHJAX]

in linear time. The complexity is linear to the maximum $$$n$$$ plus the number of testcases.
  • »
    »
    13 months 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 :(

    • »
      »
      »
      13 months 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

      Unable to parse markup [type=CF_MATHJAX]

      )