Half-consecutive Numbers

给出 t i = i ( i + 1 ) 2 t_i=\frac{i(i+1)}{2} ti​=2i(i+1)​,给出一个n要求求出满足以下条件的i的最小值

1,i>=n

2, t i t_i ti​是一个平方数( t i = = k ∗ k t_i==k*k ti​==k∗k)

关键在第二个条件，什么情况下他才是平方数呢，思考后可以得到以下两种情况

1,如果 i i i是奇数, i + 1 i+1 i+1是偶数—— i i i是平方数且 i + 1 2 \frac{i+1}{2} 2i+1​也是平方数

2,如果 i + 1 i+1 i+1是奇数, i i i是偶数—— i + 1 i+1 i+1是平方数且 i 2 \frac{i}{2} 2i​也是平方数

偶数的平方是偶数，奇数的平方是奇数。想到这一点这题就不难了。

我们可以把所有符合条件的i全部求出来，排序后二分就可以求出>=n的最小值了

因为偶数除以2以后不知道奇偶性，所以奇数更好处理，我们可以枚举1到 n \sqrt{n} n

​的奇数k，显然kk是一个平方数，然后我们把kk对应以上两种情况里面的奇数项，然后验证偶数项是不是平方数就好了，如果是，把kk相应的i加入数组：

对于情况1，i是平方数kK，验证 i + 1 2 \frac{i+1}{2} 2i+1​是不是平方数，将i(kk)push

对于情况2，i+1是平方数kK，验证 i 2 \frac{i}{2} 2i​是不是平方数，将i(k*k-1)push

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
inline LL read()
{
	LL kk=0,f=1;
	char cc=getchar();
	while(cc<'0'||cc>'9'){if(cc=='-')f=-1;cc=getchar();}
	while(cc>='0'&&cc<='9'){kk=(kk<<1)+(kk<<3)+cc-'0';cc=getchar();}
	return kk*f;
}
vector<LL>v;
bool check(LL x)
{
	if(x<=0)return 0;
	LL a=sqrt(x);
	if(x==a*a)return 1;
	return 0;
}
int main()
{
	int T=read();
	for(LL i=1;i<=100000022;i+=2)
	{
		LL k=i;
		if(check(((k*k+1)/2)))v.push_back(k*k);
		if(check(((k*k-1)/2)))v.push_back(k*k-1);
	}
	sort(v.begin(),v.end());
	for(int ii=1;ii<=T;++ii)
	{
		LL asd=*lower_bound(v.begin(),v.end(),read());
		printf("Case #%d: %lld\n",ii,asd);
	}
	return 0;
}