I heartily thank Clive Fraser (aka CSFPython) for the idea, description and examples on this task - and Mathias Kern (aka gardengnome) for hinting me on how to implement it :)
The Least Common Multiple or LCM of a set of numbers is a well-known concept. It can be defined as follows: The LCM of a set of numbers is the smallest positive integer which is exactly divisible by each of the numbers in the set. For example, LCM(14,20) = 140 and LCM(3,6,10) = 30.
We already have seen and calculated LCM of two values in the GCD task.
To extend this to several values we can follow obvious rule:
LCM(a, b, c, ..., y, z) = LCM(a, LCM(b, LCM(c, LCM(..., LCM(y, z)))))
i.e. calculate LCM of any two, then LCM of result and next one, and so on, until all values are included.
We can also define the LCM of a range of numbers e.g.
LCM(2...5) = LCM(2,3,4,5) = 60
LCM(10...15) = 60060
As the range of numbers increases the value of the LCM tends to increase rapidly.
For example LCM(40...60) = 4224373219170545641200. Since we will be dealing with very big numbers
we will give all of the results modulo 1000000007 (i.e. 10^9 + 7).
So LCM(40...60) mod 1000000007 = 933314007.
Input data
First row is the number (N) of test-cases.
Next N lines contains pairs A B - starts and ends of ranges (A <= B < 10000000).
Answer Should give LCM for every range, i.e. LCM(A, A+1, A+2, ..., B-1, B), by modulo 1000000007.
Example:
input:
4
10 15
40 60
5728 9708
6119950 9666068
answer:
60060 933314007 587266328 562476460
Note on performance by the author: If your computer does not crash from the demands made on its resources and you get a correct solution after half a day of program execution time, then you deserve to claim the solution for sheer persistence! However, that defeats the object of the problem. You should look for an efficient solution. My experiments in Python (usually significantly slower than other languages) give times of just under 1 minute for what I think will be the most likely method. However, there is a better one, which executes about 100 times faster and has a significantly shorter and simpler program...