HDU 4279 Number------法則の問題を探します

Number
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2159    Accepted Submission(s): 614
Problem Description
　　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.
 
 
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
2
1 1
1 10
Sample Output
0
4
 
この問題は、同じように考えのない問題です.
ある人は、1000 ms、テーマが複雑で、法則を探していると思っています.この法則は.......
1->x : ans
            1-1:0
            1-2:0
            1-3:0
            1-4:0
            1-5:0//xが5以下になるまで0です.5/2-2 = 0
            1−6:1//xはある数の二乗和であり、kは偶数である.6/2-2=1に変わりません.
            1−7:1//xはある数の二乗和であり、kは偶数である.7/2-2=1に変わりません.
            1-8:2    
            1−9:3//xは、ある数kの二乗和であり、kは奇数である.プラス1  9/3-2 + 1 = 3;
            1-10:4
            1-11:4
            1-12:5
            1-13:5
            1−14:6//xは、ある数kの二乗和であり、kは奇数である.プラス1  14/2-2 + 1 = 6;
            1-15:6
            1−16:6//xは、ある数kの二乗和であり、kは偶数である.変わらない  16/2-2 = 6;
            1-17:6
            1-18:6
            1-19:7
            1-20:8
            1-21:8
            1-22:9
            1-23:9
            1-24:10
            1−25:11//xは、ある数kの二乗和であり、kは奇数である.プラス1   25/2 -2 + 1 = 11;
            1-26:12
また区間を考慮した問題は[n,m]=[1,m]−[1,n−1]を求める.

 1 /*

 2     ，        ，

 3       

 4           

 5 

 6 */

 7 

 8 #include<stdio.h>

 9 #include<math.h>

10 #include<stdlib.h>

11 

12 __int64 make_ini(__int64 num)

13 {

14     __int64 tmp=num;

15     if(num<6)

16     return 0;

17     tmp=(num>>1)-2;

18     num=(__int64)sqrt(num*1.0);

19     if(num%2==1)

20     tmp++;

21     return tmp;

22 }

23 

24 int main()

25 {

26     __int64 T,n,m;

27     while(scanf("%I64d",&T)>0)

28     {

29         while(T--)

30         {

31             scanf("%I64d%I64d",&n,&m);

32             printf("%I64d
",make_ini(m)-make_ini(n-1));

33         }

34         return 0;

35     }

36     return 0;

37 }