Number
time limit per test 1 second memory limit per test 256 megabytes
Here are two numbers A and B (0 < A <= B). If B cannot be divisible by A, and A and B are not co-prime numbers, we define A as a special number of B.
  For each x, f(x) equals to the amount of x’s special numbers.
  For example, f(6)=1, because 6 only have one special number which is 4. And f(12)=3, its special numbers are 8,9,10.
  When f(x) is odd, we consider x as a real number.
  Now given 2 integers x and y, your job is to calculate how many real numbers are between them.

传送门:HDU4279

Input

In the first line there is an integer T (T <= 2000), indicates the number of test cases. Then T line follows, each line contains two integers x and y (1 <= x <= y <= 2^63-1) separated by a single space.

Output

Output the total number of real numbers.

Sample Input

1
2
3
2
1 1
1 10

Sample Output

1
2
0
4

题解

两个性质要掌握 1.欧拉函数f(n)即1-n中有多少个数与n互质 当n>2时 f(n)必是偶数 2.因数的个数等于分解的所有因数的阶数加一相乘 所以对非平方数 因数的个数肯定为偶数 而完全平方数的因数个数为奇数 这道题分类讨论就行了 其他博客写得很详细 主要有一点c++sqrt精度会有问题 java也是 所以手写了一个二分sqrt过了(java写起来方便 因为可用BigInteger防溢出)
## AC code:(不包含输入类)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.io.*;  
import java.math.BigInteger;
import java.util.*;
public class Main {
public static void main(String[] args) {
FastScanner sc=new FastScanner();
PrintWriter pw=new PrintWriter(System.out);
int n=sc.nextInt();
while(sc.hasNext()){
long a=sc.nextLong();
long b=sc.nextLong();
pw.println(js(b)-js(a-1));
pw.flush();
}

}
static int gcd(int a,int b){
return a==0?b:gcd(b%a,a);
}
static long js(long n){
if(n<6)return 0;
return n/2-1+((maxsqrt(n)%2==1)?0:-1);
}
static long maxsqrt(long n){ //自己写的sqrt
long start=1;
long end=n;
long res=-1;
while(start<=end){
long mid=(start+end)/2;
if(BigInteger.valueOf(mid).multiply(BigInteger.valueOf(mid)).compareTo(BigInteger.valueOf(n))<=0){
res=mid;
start=mid+1;
}else{
end=mid-1;
}
}
return res;
}
}