当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

[规律题]zoj 3629:Treasure Hunt IV

发表于: 2012-08-31   作者:暴风雪   来源:转载   浏览:
摘要: 大致题意:     现在规定数字n,如果[n/1] + [n/2] + ... + [n/k] + ...是偶数,则这个数字是一个特殊数字。现在给出两个数a,b,求在[a,b]这个闭区间内有多少个那样的特殊数字。   大致思路:     (0 <= a <= b <= 2^63-1),暴力必然超时,这里先写一个暴

大致题意:

    现在规定数字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;
}
 

[规律题]zoj 3629:Treasure Hunt IV

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号