|
||||||||||
Pty loves lcmTime Limit: 10000/5000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 61 Accepted Submission(s): 18 Problem Description lcm($x_1,x_2,...,x_k$) is the least common multiple of {$x_1,x_2,...,x_k$}. $\phi (x)= {\sum_{y=1}^x} [gcd(x,y)=1]$ Define function f(x,y) = lcm(x,x + 1,...,y-1,y)(x < y)(both x,y are non-negative integers) Now Pty wants to know $\sum_{x=1}^{+\infty }$$\sum_{y=x+1}^{+\infty}$$\phi (f(x,y)) \times [L ≤ f(x,y) ≤ R]$ modulo $2^{32}$. Input The first line contains a single integer T(1 ≤ T ≤ 50)— the number of test cases. The only line of each test case contains two integers L,R(1 ≤ L ≤ R ≤ $10^{18}$). Output For each test case, output the answer modulo $2^{32}$. Sample Input
Sample Output
Source | ||||||||||
|