程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 4279 Number

hdu 4279 Number

編輯:C++入門知識

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; 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved