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;
}