二分查找+数学 HDOJ 4342 History repeat itself
2024-08-30 06:32:38
题意:计算从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\n", ans1, ans2);
} return 0;
}
最新文章
- Java线程:线程状态的转换
- JAVA 注解的几大作用及使用方法详解
- redhat 6 / centos 6 搭建Django环境
- Poj 1511 Invitation Cards(spfa)
- webservice一片:其中在外线呼叫数据,查看返回数据
- mysql解决中文乱码问题
- [HAOI2006]受欢迎的牛
- iOS----------The Apple Developer Program License Agreement has been updated.
- Mybatis的updateByExampleSelective方法
- python学习之-用scrapy框架来创建爬虫(spider)
- js 格式化时间
- R语言-增加图例
- JS文件的写入
- 5.6 Components -- Handling User Interaction with Actions
- css控制同一个页面的两个表格,一个显示有边框线,而另一个没边框线
- 数据集DataSet
- css中:not()选择器和jQuery中.not()方法
- Lucene笔记一
- java PinYinUtils 拼音工具类
- java程序——输入判断成绩