maksyuki 发表于 oj 分类,标签:

1007 - Mathematically Hard

In this problem, you will be given two integers a and b. You have to find the summation of the scores of the numbers from a to b (inclusive). The score of a number is defined as the following function.Mathematically some problems look hard. But with the help of the computer, some problems can be easily solvable.

score (x) = n2, where n is the number of relatively prime numbers with x, which are smaller than x

For example,

For 6, the relatively prime numbers with 6 are 1 and 5. So, score (6) = 22 = 4.

For 8, the relatively prime numbers with 8 are 1, 3, 5 and 7. So, score (8) = 42 = 16.

Now you have to solve this task.


Input starts with an integer T (≤ 105), denoting the number of test cases.

Each case will contain two integers a and b (2 ≤ a ≤ b ≤ 5 * 106).


For each case, print the case number and the summation of all the scores from a to b.

Sample Input

Output for Sample Input

36 68 82 20 Case 1: 4Case 2: 16Case 3: 1237




算法分析:使用递推的方法将5e6以内的欧拉函数值算出来,进而求前缀和,最后直接查询即可,注意本题数据比较大,只能使用unsigned long long定义euler数组