[规律题]zoj 3629：Treasure Hunt IV

大致题意：

    现在规定数字n，如果[n/1] + [n/2] + ... + [n/k] + ...是偶数，则这个数字是一个特殊数字。现在给出两个数a,b，求在[a,b]这个闭区间内有多少个那样的特殊数字。

 

大致思路：

    (0 <= a <= b <= 2^63-1)，暴力必然超时，这里先写一个暴力程序就能找到规律。

    [0,1)

    [4,9)

    [16,25)

    [36,49)

    ……

    这些区间内的都是特殊数字，然后按造规律写出代码即可

 

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;

long long solve(long long n)
{
    if(n<0)return 0;
    long long a=sqrt(n),res;
    if(a%2==1)
    {
        long long b=sqrt(n)-1;  //a*a---b*b---------a
        long long c=b/2+1;    //第几项
        res=(1+b*2+1)*c/2;
        return res;
    }
    else
    {
        long long b=sqrt(n);  //a*a---b*b---------a
        long long c=b/2+1;    //第几项
        res=(1+b*2+1)*c/2;
    //    cout<<b<<" "<<c<<" "<<res<<endl;
        res-=(pow(b+1,2)-n-1);
        return res;
    }
}

int main()
{
    long long a,b;
//    while(cin>>a)
//    {
//        cout<<solve(a)<<endl;
//    }
    while(cin>>a>>b)
    {
        cout<<solve(b)-solve(a-1)<<endl;
    }
    return 0;
}