_Hridoy's blog

Seek Help!
By _Hridoy, history, 7 months ago, In English

Hello my cp mates, I am stucked in a problem suppose I have to find sum of gcd(i,k) for all number i from 1......N. Here N is so big around N<=10^12. So we can't iterate through all the numbers from 1 to N. Have any alternative way???

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been updated by _Hridoy (previous revision, new revision, compare).

→ Reply
»
7 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Solving this problem requires some knowledge of inversion,

$$$ g=f*\mu\\ \sum \gcd(i,n)=\sum\sum_{d|n}g(d) \\ =\sum_{d|n}\frac{n}{d}g(d) \\ g=\varphi \\ \sum_{i=1}^n\gcd(i,n)=\sum_{d|n}\frac{n}{d}\varphi(d) $$$

Then divide this equation into number theory blocks. Using Some Sublinear Sieves to Process Euler Functions For example, Du Jiaosieve.

→ Reply