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

Seek Help!
Автор _Hridoy, история, 13 месяцев назад, По-английски

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???

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

»
13 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

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

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.

→ Ответить