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 109+7
Input
First line consists of T = number of test cases, next T line will contain a and b.
Output
For each T lines, print the required output.
Constraints
T ≤ 100000
1 ≤ a ≤ b ≤ 1000000
Example
Input:
3
1 6
10 15
41 90
Output:
66
675
139860
hide comments
Ishan:
2023-03-24 06:12:29
@Mitch Now that I have solved it, can I know your solution? You can add my gmail for a private chat, it's same as my handle. |
|
Kanish_The_Vista:
2014-04-19 17:31:43
@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... |
|
Zeus:
2014-04-11 13:55:18
@admin can you please tell me why am i getting runtime error ???? i think my algo is correct... please help... id: 11425187
|
|
Somesh Maurya™:
2013-08-22 04:54:11
in 0.04 sec???how man?? |
|
Mitch Schwartz:
2013-06-29 21:39:58
@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. |
|
Yashpal:
2013-06-29 21:30:36
Can someone give me some link so that i can learn more about sum of the LCM....
|
|
Hariharan :
2013-06-17 19:19:41
used euclid's algorithm to find the lcm, but i'm still getting TLE. I wonder how Mitch solved it under 0.04s!!!!
|
|
Ashish Lavania:
2012-12-25 13:00:54
nice! first try AC!! |
|
Runtime Error:
2012-04-10 23:10:30
tle :( |
Added by: | avinash |
Date: | 2012-04-08 |
Time limit: | 2.772s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | own |