ADDLCM - lcm addition
Mao is very good in mathematics, he likes to play with numbers and number theory is his favorite chapter. Once he decided to give a question to kalyu his friend . Now Kalyu is always busy in writing articles, as he likes maths but articles is his passion and source of income too, so he can’t give much time solving that maths question, but he too don’t want to hurt his friend, so help kalu in his problem ?
Given a,b such that a<=b calculate the addition:-
LCM(a,b) + LCM(a+1,b) + .. + LCM(b,b), where LCM(a,b) denotes the Least Common Multiple of the integers a and b.
Since, output may be very large, take the mod 10^9+7
First line cosists of T=number of test cases, next T line will contain a and b
For each T lines, print the required output.
1 <= a <= b <= 1000000
@AVINASH can u check my submission id:11465975,i m getting tle...i think so my algo is working fine but don't know why it does not pass the judge time...
@admin can you please tell me why am i getting runtime error ???? i think my algo is correct... please help... id: 11425187
in 0.04 sec???how man??
Last edit: 2013-08-22 04:54:24
@Yashpal, Hariharan: I didn't find any published work about this, it was a lot of work on paper, and I think it's a great problem. You may find it useful to work on LCMSUM first, it's related to this one and easier.
Can someone give me some link so that i can learn more about sum of the LCM....
used euclid's algorithm to find the lcm, but i'm still getting TLE. I wonder how Mitch solved it under 0.04s!!!!
nice! first try AC!!