### proveus's blog

By proveus, history, 13 months ago,

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

 » 13 months ago, # | ← 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 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, # ^ |   +10 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, # ^ |   0 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])