zcmu 2014: 一生之敌（思维）

【题目】

2014: 一生之敌

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 725  Solved: 117
[Submit][Status][Web Board]

Description

Input

 第一行输入一个整数T，表示数据组数。  
每组数据输入一个整数n。

 1 <= T <= 100000 
 0 <= n <= 10^19
保证结果存在 

Output

 输出一个整数。

Sample Input

3  
2  
6  
100 

Sample Output

6
6
114

【题解】

因为b^2=2*a*(a+1)^2<=1e19，所以a<=3e6

b*b=2*a*(a+1)*(a+1) --> b=sqrt(2*a)*(a+1)        枚举i=sqrt(2*a)，a=i*i/2  ，则b=i*(a+1)

数据比较大需要用unsigned long long

【代码】

#include<bits/stdc++.h> 
using namespace std; 
typedef unsigned long long ull; 
vector <ull> vec; 
main() 
{ ull i,a=0,n; for(ull i=0;a*(i+1)<=1e19;i+=2) { a=i*i/2; vec.push_back(i*(a+1)); } int t; scanf("%d",&t); while(t--) { scanf("%llu",&n); int ans=lower_bound(vec.begin(),vec.end(),n)-vec.begin(); printf("%llu\n",vec[ans]); } 
}