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 = (nn*(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.
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.
i think this link helps…!!