wustoj(脑洞)

蔚落 2022-06-04 00:47 233阅读 0赞

问题描述:

生活在另一个平行宇宙中的HLD，是一个杰出的数学家，他在20岁时就发现了超奇异质数。

作为数学家的他当然是很热爱数字的啦！这天他心血来潮想见识一下传说中的小学奥数题，于是他随便找了一道小学奥数题，聪明如他，没过多久他便想出来了，并准备算出答案。

这个题目是:把自然数 0,1，2，3，4，5，6，7，8，9，10，11，12，... 作为字符串拼接起来，求拼接后的字符串中第n个位置的数字是多少。那么那个字符串就是0123456789101112131415161718192021......所以当n=0时，答案为0，当n=1时，答案为1，当n=17时，答案为3。

但是手写运算量太大，所以HLD想请你帮忙解决这个问题。

## Input ##

多组输入数据。每行 1个整数 n。 (0<=n<=1e18)

## Output ##

每行输出一个整数。

## Sample Input  ##

## Sample Output ##

题目分析:我们为了确定是那个数字，首先做的是确定这个数字在那个数字里面。可以发现一位数有9个，俩位是90个，三位数900个，依次类推。我们根据这个可以先确定去那个数字的数位。然后就是找到那个数，接下来就是看那是第几位了。细节看代码

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #define ll long long
    using namespace std;
    
    int main()
    {
        ll n;
        while (scanf("%lld",&n)!=EOF) {
             if (n==0) {
                printf("0\n");
             }
             else {
                ll sum=0,res;
                int len;
                for (int i=1;i<=18;i++) {
                    res=1;
                    for (int j=1;j<i;j++) {
                        res=res*10;
                    }
                    sum+=(res*9*i);
                    if (sum>=n) {
                        len=i;
                        break;
                    }
                }
               // cout<<len<<endl;//确定位数
                sum-=(res*9*len);
                sum++;
                ll cnt=n-sum;
               // cout<<cnt<<endl;
                cnt=cnt/len;
                ll a=res+cnt;//确定是那个数
               // cout<<a<<endl;
                ll b=n-sum-len*cnt;//确定是第几位
               // cout<<b<<endl;
                ll num=0;
                if (len-b-1>=1) {//把后面的0除掉
                for (ll i=1;i<=len-b-1;i++) {
                    a=a/10;
                }
                }
                printf("%lld\n",a%10);
             }
        }
        return 0;
    }