How to solve this question. Doing it in general way will result in TLE.

Well, one way i can tell you is to precompute the value of sum for all n from 1 to 1000000 and store it in an array. Then simply print the value corresponding to whatever n is asked. However, this isn’t a very good method but will solve your problem. Few things which you could consider before solving this problem are :-

1.) HCF * LCM = product of numbers. Finding HCF with euclid’s is faster than finding LCM anyway.

2.) If n is prime then gcd of all numbers from 1 to n-1 will be n. Hence sum will be (n(n-1)/2 )*n. And the lcm of n and n is n. so final sum = (n*n*(n-1))/2 + n.

Using these, you can first compute the results for all n from 1 to 1000000 in another program and store its outputs in an array (initialize) and simply print them at a later time whenever required.

i think this link helps…!!

Hello u_k11

I tried alot to understand the solution to this problem. Solution is somewhat mathematical.

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.

I am also looking for proof if i find any thing useful for you. i will definately update it here.