Least common multiple
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 451 Accepted Submission(s): 151
Problem Description
bobo has an integer set S={x1,x2,…,xn}, where xi=2ai * 3bi.
For each non-empty subsets of S, bobo added the LCM (least common multiple) of the subset up. Find the sum of LCM modulo (109+7).
Input
The input consists of several tests. For each tests:
The first line contains n (1≤n≤105). Each of the following n lines contain 2 integers ai,bi (0≤ai,bi≤109).
Output
For each tests:
A single integer, the value of the sum.
Sample Input
Sample Output
思路：最小公倍数只能是形如2^a * 3^b，而每次求一种最小公倍数 2^i * 3^j 的和只需要考虑小于等于i 和 j 的集合总数就好了，这个计数可以用线段树来完成，按a从小到大的顺
