zoj3629 Treasure Hunt IV

zoj3629 Treasure Hunt IV

思路：找規律，發現符合要求的數為

[0,1)

[4,9)

[16,25)

[36,49)

…………

[n^2 , (n+1)^2)

發現 n^2 到（n+1）^2（n為偶數）前開後閉的區間為符合要求的數，然後發現（n+1）*（n+1）-n*n組成的數列為一個差值為4等差數列，我們需要求區間[a,b]符合要求的數，那麼只需要用b前面符合要求的數減去a-1中符合要求的數。。。。。

開始的時候一直WA，到後才發現輸入輸出時用的%I64d要換成%lld，悲劇呀。。。。。。

code：

#include
#include
#include
#include
using namespace std;

typedef long long LL;

LL f(LL x)   //計算0到x之間符合要求的數，等差數列首項看為1
{
    if(x==-1) return 0;
    LL a=sqrt(x);
    LL sum=0;
    if(a*a==x)
    {
        LL n=(a+1)/2;
        sum=n+n*(n-1)*2;
        if(a%2==0)
        {
            sum++;
        }
    }
    else if(a*a