二分查找+数学 HDOJ 4342 History repeat itself-白红宇

二分查找+数学 HDOJ 4342 History repeat itself

阅读量：6980 次

发布时间：2019-06-27

本文共 1220 字，大约阅读时间需要 4 分钟。

题意：计算从1开始到第n个非完全平方数的开方和

分析：设第n个非完全平方数的值为a，x * x < a < (x+1) * (x+1)，而且易得(tmp = sqrt (a) ) == x，a之前的非完全平方数的个数为a - tmp，所以可以二分查找a - tmp == n的a，然后模拟一下能计算出前a个数的开方和

收获：二分查找是个好方法

代码：

/************************************************* Author        :Running_Time* Created Time  :2015-8-27 16:14:57* File Name     :C.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef long long ll;const int N = 1e5 + 10;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;int main(void) { int T; scanf ("%d", &T); while (T--) { int n; scanf ("%d", &n); ll l = 1, r = 1e12, ans1 = 0, ans2 = 0; while (l <= r) { ll mid = (l + r) >> 1; ll tmp = sqrt (mid); if (mid - tmp == n) { ans1 = mid; if (tmp * tmp == mid) ans1--; break; } else if (mid - tmp > n) r = mid - 1; else l = mid + 1; } ll tmp = sqrt (ans1); for (ll i=1; i

转载于:https://www.cnblogs.com/Running-Time/p/4765521.html

你可能感兴趣的文章