2017 ACM-ICPC 亚洲区（乌鲁木齐赛区）网络赛E Half-consecutive Numbers

43 阅读 0 评论 29 点赞

我是靠谱客的博主顺利皮带，最近开发中收集的这篇文章主要介绍2017 ACM-ICPC 亚洲区（乌鲁木齐赛区）网络赛E Half-consecutive Numbers，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

time limit
2000ms
memory limit

131072KB

The numbers 1 , 3 , 6 , 10 , 15 , 21 , 28 , 36 , 45 and t(i) = [i(i + 1) ] / 2, are called half-consecutive.
For given N , find the smallest r which is no smaller than N such that t(r) is square.

Input Format
The input contains multiple test cases.
The first line of a multiple input is an integer T followed by T input lines.

Each line contains an integer N (1 ≤ N ≤ 10 ) .

Output Format
For each test case, output the case number first.
Then for given N , output the smallest r .

If this half-consecutive number does not exist, output −1 .

Sample Input
4
1
2
9

Sample Output
Case #1: 1
Case #2: 8
Case #3: 49

Case #4: 288

题意：定义自然数的前 i 项和为 half-consecutive；给定一个数N，t(r) 是个平方数，找到不小于N且离N最近的 r 是多少。

思路：数论先打表；

打表完就找到规律了：

i x^2 x

1: 1 1
8: 36- 6
49: 1225- 35
288: 41616- 204
1681: 1413721- 1189
9800: 48024900- 6930
57121: 1631432881- 40391
332928: 55420693056- 235416
1940449: 1882672131025- 1372105
11309768: 63955431761796- 7997214

开放数有规律，每个平方数的开方与对应的i有规律；

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll stop=10000000000000000;
const int N=1000006;
ll chazhi[N],square[N],bianhao[N];
int main()
{
square[1]=1,square[2]=6;
int i;
for( i=3;; i++)
{
square[i]=6*square[i-1]-square[i-2];
if(square[i]>=stop)
break;
}
chazhi[1]=0,chazhi[2]=2,chazhi[3]=14;
for(int j=4; j<=i; j++)
{
chazhi[j]=chazhi[j-1]*6-(chazhi[j-2]-2);
}
for(int j=1; j<=i; j++)
{
bianhao[j]=chazhi[j]+square[j];
}
//
for(int j=1; j<=i; j++)
//
printf("%I64d ",bianhao[j]);
//
printf("n");
int t,cas=0;
scanf("%d",&t);
while(t--)
{
ll x;
scanf("%lld",&x);
ll ans=lower_bound(bianhao+1,bianhao+1+i,x)-bianhao;
//
if(bianhao[ans]>)
if(bianhao[ans]>stop)
printf("Case #%d: -1n",++cas);
else
printf("Case #%d: %lldn",++cas,bianhao[ans]);
}
return 0;
}