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

题目传送门

题意：计算从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 <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std;

#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef 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<tmp; ++i)	{
			l = i * i, r = (i + 1) * (i + 1);
			ans2 += (r - l) * i;
		}
		ans2 += (ans1 - tmp * tmp + 1) * tmp;
		printf ("%I64d %I64d
", ans1, ans2);
	}

    return 0;
}