算法思想

预处理数字位数的累计和 确定第 k 位所在的数字长度范围 计算具体数字和位置 提取数字并计算结果

代码实现

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
#define LL long long
vector<LL>g[2];
LL a[20],b[20];
LL max_int=2147483647;
void init()
{
    g[0].push_back(0);
    g[1].push_back(0);
    LL x=9,y=10;
    for(int i=1; i<=18; ++i,x=x*10+9,y*=10)
    {
        g[0].push_back(x);
        g[1].push_back((LL)(sqrt(y)-0.00001));
    }
    LL o=10;
    for(int i=1; i<=10; ++i,o*=10)
    {
        a[i]=a[i-1]+i*(o-o/10);
    }
    for(LL i=1; i<=18; ++i)
    {
        b[i]=b[i-1]+i*(g[1][i]-g[1][i-1]);
    }
}
int getl(LL n)
{
    int ans=0;
    while(n) ans++,n/=10;
    return ans;
}
int get_a(LL n)
{
    LL l=1,r=999999999;
    while(l<r)
    {
        LL mid=l+(r-l)/2;
        LL len=getl(mid);
        LL s=a[len-1]+(len*(mid-g[0][len-1]));
        if(s>n)
        {
            r=mid;
        }
        else if(s<n)
        {
            l=mid+1;
        }
        else
        {
            return mid%10;
        }
    }
    LL len=getl(l);
    LL s=a[len-1]+(len*(l-g[0][len-1]));
    while(s>n) s--,l/=10;
    return l%10;
}


int get_b(LL n)
{
    LL l=1,r=317227766;
    while(l<r)
    {
        LL mid=l+(r-l)/2;
        LL len=getl(mid*mid);
        LL s=b[len-1]+(len*(mid-g[1][len-1]));
        if(s>n)
        {
            r=mid;
        }
        else if(s<n)
        {
            l=mid+1;
        }
        else
        {
            return mid*mid%10;
        }
    }
    LL len=getl(l*l);
    LL s=b[len-1]+(len*(l-g[1][len-1]));
    l=l*l;
    while(s>n) s--,l/=10;
    return l%10;
}

int main()
{
    LL n;
    init();
    while(scanf("%lld",&n)!=EOF)
    {
        if(!n) break;
        LL a=get_a(n),b=get_b(n),
           c=get_a(n+1),d=get_b(n+1),jin=0;
        while(c+d>8)
        {
            if(c+d>9)
            {
                jin=1;
                break;
            }
            n++;
            c=get_a(n+1);
            d=get_b(n+1);
        }
        cout<<(a+b+jin)%10<<endl;
    }
    return 0;
}