Time Limit: 2 second(s) | Memory Limit: 64 MB |
Mathematically some problems look hard. But with the help of the computer, some problems can be easily solvable.
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.
score (x) = n^{2}, 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) = 2^{2} = 4.
For 8, the relatively prime numbers with 8 are 1, 3, 5 and 7. So, score (8) = 4^{2} = 16.
Now you have to solve this task.
Input starts with an integer T (≤ 10^{5}), denoting the number of test cases.
Each case will contain two integers a and b (2 ≤ a ≤ b ≤ 5 * 10^{6}).
For each case, print the case number and the summation of all the scores from a to b.
Sample Input |
Output for Sample Input |
3 6 6 8 8 2 20 |
Case 1: 4 Case 2: 16 Case 3: 1237 |
Euler's totient function applied to a positive integer n is defined to be the number of positive integers less than or equal to n that are relatively prime to n. is read "phi of n."
Given the general prime factorization of , one can compute using the formula
Developed and Maintained by
JANE ALAM JAN |
Copyright © 2012
LightOJ, Jane Alam Jan |