Small number theory technician

Revision en1, by 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.

Tags number theory, help me

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English VIRUSGAMING 2023-10-01 05:22:24 446 Initial revision (published)