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

[规律题]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

    震惊

    震惊

编辑推荐
Taiko taiko Time Limit: 1000ms Memory Limit: 65536KB 64-bit integer IO format: %lld Java clas
1049:选一坐标点建房。河水淹没区域是半圆形,每年扩大50平方英里。问几年能淹到房子。 Sample Input
Number of Containers Time Limit: 1 Second Memory Limit: 32768 KB For two integers m and k, k
Counting Triangles Time Limit: 2 Seconds Memory Limit: 65536 KB Given an equilateral triangle
最近股市很热,连我这平常不炒股的码农也开始炒股了。但是因为对这个新的领域不熟悉,虽然没被套住
Product Hunt,目前国外非常火的互联网产品分享平台,用户可以分享自己喜欢的产品,只需附上对应的
1.关于本博客的说明 Code Hunt 是我从CSDN上的一篇文章中无意间看到的:微软研究院正式发布编程学习
G - Cylinder Candy Time Limit:2000MS Memory Limit:65536KB 64bit IO Format:%lld & %llu Submit
Superbot Time Limit: 2 Seconds Memory Limit: 65536 KB Superbot is an interesting game which y
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1586 <img src="http://img.it6
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号