HDU 4279（數學+找規律）

題意：定義：special number：如果B不能能被A整除，且A和B不是互質的，那麼就稱A是B的special number。(0 < A <= B)

                     f[x]：數字x所擁有的special數。

                     real number:當數字x的f[x]是奇數時，則數字x就是real number。

           求解：給出x和y，求出從x到y一共有多少個real number。

分析：因為x和y都很大(1 <= x <= y <= 2^63-1)，而時間又很短，是以不可能直接求出，隻可能存在某種規律。為了找出其規律我們對其打表。

              由于輸出x和y之間的數，是以隻要求出從1到x和1到y數的個數，最後結果為[y]-[x-1]即可。

           對其打表:

           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

          是以找到的規律如下：分析了上面的資料知道，初始化ans = x/2-2，我們隻要去考慮這個數的是開平方後的整數是奇數還是偶數即可，如果是偶數則不加1，如果是奇數則加1

          這裡判斷奇數和偶數可以利用為運算"&"來判斷，隻要做x&1即可，如果x是偶數那麼x的二進制的最後一位為0，如果是奇數那麼二進制數的最後一位是1.

          資料量很大，資料類型要為long long 或 __int64.有時候用long long 會出錯，可以換成__int64即可。

//HDU 4279,數學+找規律
#include<cstdio>
#include<cmath>
using namespace std;

int t;
__int64 x,y;

__int64 solve(__int64 xx)
{
    if(xx<=5)
        return 0;
    __int64 ans;
    ans=xx/2-2;
    xx=sqrt(xx);
    if(xx&1)
        ans++;
    return ans;
}

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%I64d%I64d",&x,&y);
        __int64 ans1=solve(y);
        __int64 ans2=solve(x-1);
        __int64 ans=ans1-ans2;
       printf("%I64d\n",ans);
    }
    return 0;
}