hiho一下 第180周 Nature Numbers

題目1 : Nature Numbers

時間限制:10000ms

單點時限:1000ms

記憶體限制:256MB

描述

Consider the following sequence S which is constrcuted by writting nature numbers one by one: “012345678910111213…”.

The first digit of S, S[0], is 0. The second digit S[1] is 1. And the 11th digit S[10] is 1.

Given an integer N, can you find the digit S[N]?

輸入

An integer N. (0 <= N <= 1018)

輸出

Digit S[N].

樣例輸入

17
           

樣例輸出

3
           

題解：

一個直覺的解法是從1, 2, 3, … 開始一個數一個數枚舉。一開始count=0，儲存位數之和。

假設目前枚舉到K，我們就把count加上K的位數。如果這時count大于等于N，我們就知道第N位應為K的倒數第N-K+1位。

考慮到N=10^18時，K至少大于10^16，這個算法肯定會逾時。

一種優化的思路是不要一個數一個數枚舉，而是一批數一批數枚舉：每次枚舉所有的一位數、兩位數、三位數……

一位數有10個(包括0)，兩位數有90個，三位數有900個……

假設目前枚舉到K位數，我們就把count加上(K * K位數的個數)。如果這時count大于等于N，我們就知道第N位是一個K位數的某一位。

當然具體是第幾個K位數的第幾位，也可以計算出來。請大家自己算一算~

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long  n,s,num,i,ans;
    cin>>n; // 假定n 為20;
    if(n==) puts("0");
    else
    {
        s=,num=,i=;     // i代表位數, num代表i位數有多少個, s目前位數和
        while(n>=s+num*i)  //  判斷 s[n]出現在幾位數裡
        {
            s+=num*i;
            i++;
            num*=;
        }
        n-=s; //20-9=11       //為了找到s[n] 出現在哪個整數裡, 減去執之前位數不同的數
        num=(num/)-;  //9   //上一個位數有幾個
        num+=n/i;    //9+11/2=14  //num 表示 s[n] 代表的整數
        n%=i;    //11%2=1       //
        if(n==)  printf("%d\n",num%);  //若n為最後一位，直接輸出最後一位
        else
        {
             num++; 
             stack<int> p;
             while(num) p.push(num%), num/=; // 5 1
             while(n)
             {
                ans=p.top();
                p.pop();
                n--;
             }
             cout<<ans<<endl;
        }
     }
    return ;
}