project euler problem 350

Constraining the least greatest and the greatest least

This problem is a relatively easy one. We are given some numbers like 1e6, 1e12 and 1e18.  1e18 ruled out the possibility of any sort of brute force. 1e12 means that we need to do some optimization on the numbers from 1e6 to 1e12 since it is still a burden for computer. Well, 1e6 is not so big a number, we can do whatever we like.

After sometime's thought, I found that there is a neat formula for this problem(it is not difficult to derive the formula). With this formula, it is very easy to find the number of valid lists for certain gcd and lcm.(Well, after I read the discussion, I found that this formula may be derived after a moment's thought!) My code first ran for 5 seconds, then I did some optimization since 1e18 is too large in some sense, then the code runs for 0.18 second.