Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

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


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