wustoj(脑洞)-蒲公英云

wustoj(脑洞)

蔚落 2022-06-04 00:47 350阅读 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;
}