网站首页 关于作者

E: Half-consecutive Numberstime limit2000msmemory limit131072KBThe numbers 1, 3, 6, 10, 15, 21, 28, 36, 45 and t = i(i + 1), are called halfconsecutive.For given N, find the smallest r which is no smaller than N such that t is square.i 21rInput FormatThe 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 FormatFor 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 Input412950Sample OutputCase #1: 1Case #2: 8Case #3: 49Case #4: 288

题面乱了，我加了图片

题意，给定一个N（1到1e16），求大于等于N的最小数属于i（i+1）/2,并且此数是平方数。（没有就输出-1，因为输出的数要求也是1e16的范围，所以会有这种可能）

思路：首先数据范围是挺大的，枚举会超时，经过我对数据的分析，找到了规律。直接打表AC

第三列是平方数的根，观察可得图中规律，并且验证了的数都是正确的，因为是比赛没有去证明它，然后我们要的是第一列数据，如果直接乘的话，数据会达到1e32必然越界，显然第三列数与第一列数有关系，所以第一列数也会有一个规律。。。此规律见代码，，，之后打表AC。

还有1e16是17位数。。。当时脑抽了，这儿贡献了一次WA

 #include<bits/stdc++.h>
using namespace std;
#define LL long long
int main()
{
    LL b[25] =
    {
        1,
        8,
        49,
        288,
        1681,
        9800,
        57121,
        332928,
        1940449,
        11309768,
        65918161,
        384199200,
        2239277041,
        13051463048,
        76069501249,
        443365544448,
        2584123765441,
        15061377048200,
        87784138523761,
        511643454094368,
        2982076586042449,
        17380816062160328,
    } ;
    /*   LL a[10000],b[10000];
       a[1]=1;
       a[2]=6;
       for(int i=3; i<=25; i++)
       {
           a[i]=a[i-1]*6-a[i-2];
       }
       b[1]=1,b[2]=8;
       b[3]=49;
       b[4]=288;
       LL   k=14;
       for(int i=4; i<=25; i++)
       {
           k+=a[i-1]*2;
           // cout<<k<<endl;
           b[i]=a[i]+k;
       }

       for(int i=1; i1e16) break;
           printf("%lld,\n",b[i]);
       }
    */
    int T, cas = 1; ///b[]为第一列数，a[]为第三列数
    LL tt;
    scanf("%d", & T);
    while (T--)
    {

        scanf("%lld", & tt);
        printf("Case #%d: ", cas++);
        if (tt > 2982076586042449)
        {
            printf("-1\n");
            continue;
        }
        for (int i = 0; i < 23; i++)
            if (tt <= b[i])
            {
                printf("%lld\n", b[i]);
                break;
            }
    }

    return 0;
}