1思路：數學題+找規律
2分析：
1這一題的數據范圍很大（1---z^63-1），而給定的時間肯定才1s。那麼明顯就是找規律的題目，但是要怎麼找到這個規律呢，我們一般先用打表輸出前100或前50左右的數據找到規律就可以根據規律來寫。
2由於是要求[x,y]這個閉區間的內滿足的個數，那麼我們想到了就是相減。把[1,y]-[1,x-1]這裡為什麼不是[1,x]呢，由於這裡是閉區間那麼這裡的x是要考慮的所以不能直接減去。
3規律如下:
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.
4這裡判斷奇數和偶數可以利用為運算"&"來判斷，只要做x&1即可，如果x是偶數那麼x的二進制的最後一位為0，如果是奇數那麼二進制數的最後一位是1. 一個數除2可以用">>1"來表示這樣可以快很多。
5數據量很大，數據類型要為long long 或 __int64.有時候用long long 會出錯，可以換成__int64即可。
代碼：
[cpp]
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
typedef __int64 int64;/*類型重定義*/
#define MAXN 1010
int t;
int64 ans;
int64 Left , Right;
int64 solve(int64 x){
int64 tmp = x;
if(x < 6)
return 0;
ans = (x>>1)-2;/*初始化為這個值*/
x = sqrt(tmp);/*求出開平方的數x*/
if(x&1) /*如果是奇數則加1*/
ans++;
return ans;
}
int main(){
scanf("%d" , &t);
while(t--){
scanf("%I64d%I64d" , &Left , &Right);
printf("%I64d\n" , solve(Right)-solve(Left-1));/*這裡是solve(left-1)*/
}
return 0;
}
