Блог пользователя proveus

Number theory
Автор proveus, история, 21 месяц назад, По-английски

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.

  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

»
21 месяц назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      21 месяц назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить