HDU1597【二分瞎搞】

题意：

求第n个数；

思路：

可以看到一种序列：

123

1234

12345

123456

1234567

12345678

123456789

1234567891

12345678912

123456789123

...

那么我可以计算前 i 行数的个数（i+1）*i/2;

直接二分到离n最近的那一层，然后n-(i+1)*i/2;%9就是答案，注意还有9，9%9是0；

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

LL cal(LL n)

{

    return n*(n+1)/2;

}

LL binary_find(LL x)

{

    LL left=1;

    LL right=100000;

    while(left<right)

    {

        int mid=left+(right-left+1)/2;

        if(cal(mid)<x)

            left=mid;

        else

            right=mid-1;

    }

//    printf("left=%d\n",left);

    return cal(left);

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        LL n;

        scanf("%lld",&n);

        if(n==1)

        {

            puts("1");

            continue;

        }

        LL ans=binary_find(n);

//        printf("ans=%lld\n",ans);

        ans=n-ans;

        ans=ans%9;

        if(ans)

            printf("%lld\n",ans);

        else

            puts("9");

    }

    return 0;

}

/*

n*(n+1)/2;二分<=x的那个n;

二分类型

*/

巴特西

HDU1597【二分瞎搞】

最新文章

热门文章