Small number theory technician

Правка en1, от VIRUSGAMING, 2023-10-01 05:22:24

Hi codeforces.

Today i meet the problem that calculate:

$$$\displaystyle\sum_{i=1}^{n}\frac{n}{gcd(i,n)}$$$

and n <= 1e7 and have 1e6 testcase with n

$$$\displaystyle\sum_{i=1}^{n}\frac{n}{gcd(i,n)} = \displaystyle\sum_{i=1}^{m}t_{i} * \phi{(t_{i})}$$$

with $$$t_{i}$$$ is divisor of n and $$$\phi{(t_{i})}$$$ is euler totient function. Help me to make it fast and can run 1s on codeforces. Thanks for your help.

Теги number theory, help me

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский VIRUSGAMING 2023-10-01 05:22:24 446 Initial revision (published)