Number theory

Revision en1, by proveus, 2023-03-18 06:59:14

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.

Tags number theory

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English proveus 2023-03-18 06:59:14 335 Initial revision (published)