当前位置:编程学习 > C/C++ >>

hdu 4279 Number

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; 

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,