PROBLEM LINK:
Author and Editorialist : Shefali Chaudhary
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Euler Phi Function.
PROBLEM:
Given n, calculate the sum LCM(1,n)+LCM(2,n)+…+LCM(n,n), where LCM(i,n) denotes the Least Common Multiple of the integers i and n.
EXPLANATION:
Euler’s totient function (or Euler’s phi function), denoted as φ(n) or ϕ(n), is an arithmetic function that counts the positive integers less than or equal to n that are relatively prime to n . Thus, if n is a positive integer, then φ(n) is the number of integers k in the range 1 ≤ k ≤ n for which the greatest common divisor gcd (n, k) = 1.
Solution is somewhat mathematical to this problem. summation of LCM(i,n) for all i belongs to [1,n] is equal to ((summation of ETF(d) + 1)*n)/2 where ETF(d) is euler totient function of d and d belongs to the set of divisors of n.
You simply have to precompute the euler function for all values upto the max given constraint of 1000000. So that we can find the phi function of any given value and thus compute the result for ((summation of ETF(d) + 1)*n)/2 .
For better understanding have a look at the code of calculating the phi function in the link below: