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

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

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
  • Проголосовать: не нравится

»
4 года назад, скрыть # |
← 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.

→ Ответить