【zzuli-1626】又是A+B吗？

题目描述

其实这个题本来应该是那道撼烁古今的A+B签到题，但LCC小王子一看不乐意了，说：“这么经典的题怎么能让别人做，我们要留着自己做，马上把这道题给我换了。”于是把原本经典的A+B签到题改成了现在这道题。哎。。。啥都不说了，你们还是自己看题吧。

给你一个正整数n,找出位于序列组S1S2S3...Sk中第n个位置的数字。序列Sk就是一个从1到k的正整数序列。例如，一个80位的序列组为：11212312341234512345612345671234567812345678912345678910123456789101112345678910

输入

多实例测试。每行输入一个整数n(1<=n<=2147483647)

输出

每个测试实例输出一个整数，占一行，表示序列组第n个位置上的数字。

样例输入

8

3

样例输出

2

2

#include <bits/stdc++.h>

using namespace std;

const int N = ;

typedef long long LL;

int s[N];//s[i]代表第i组的长度

int main()

{

    int i, j;

    for(i = ; i <= N; i++)

    {

        s[i] += s[i-] + log10(i)+;

    }

    int n;

    while(~scanf("%d", &n))

    {

        LL sum = ;

        //先找到在第几组

        for(i = ; i <= N; i++)

        {

            sum += s[i];

            if(sum >= n)

                break;

        }

        sum += ;

        int ans;

        bool f = ;

        for(j = i; j >= ; j--)

        {

            int k = j;

            while(k)

            {

                if(sum == n)

                {

                    f = ;

                    break;

                }

                ans = k%;

                k /= ;

                sum--;

            }

            if(f) break;

        }

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

    }

    return ;

}