题解 | 无限长正整数排列字符串

/*
问题背景与通用原理

    无穷数列的数字分布有规律：

        1位数字（1-9）共9个，占用9个位置。

        2位数字（10-99）共90个，占用 90×2=18090×2=180 个位置。

        3位数字（100-999）共900个，占用 900×3=2700900×3=2700 个位置。

        一般化：位数为 dd 的数字有 9×10d−19×10d−1 个，占用总字符数为 d×9×10d−1d×9×10d−1。

    求解步骤：

        确定位数 dd：遍历 dd 从1开始，计算累积字符数，直到覆盖位置n。

            累积字符数公式：令 S(d)=∑k=1dk×9×10k−1S(d)=∑k=1d​k×9×10k−1。

            当 S(d−1)<n≤S(d)S(d−1)<n≤S(d) 时，n位数字属于 dd 位数的范围。

        定位具体数字：在 dd 位数范围内，计算n对应的具体整数。

            起始数字 start=10d−1start=10d−1。

            剩余位置 remain=n−S(d−1)remain=n−S(d−1)。

            数字索引 index=⌊remain−1d⌋index=⌊dremain−1​⌋（索引从0开始）。

            具体数字 num=start+indexnum=start+index。

        提取数字位：在 numnum 中提取特定位。

            位偏移 offset=(remain−1)mod  doffset=(remain−1)modd。

            将 numnum 转换为字符串，取第 offsetoffset 位字符（0-based索引）。

此方法高效（时间复杂度 O(log⁡n)O(logn)），避免了生成整个序列，适用于大n值1。
*/
#include <iostream>
using namespace std;

int main() {
    int n{};
    cin>>n;
    
    if(n<10)
    cout<<n;
    else if(n<190)
    {
        int k=n-9;
        int ptr=(k-1)/2;
        int num=10+ptr;
        
        int idx=(k-1)%2;
        if(idx==0)
        cout<<num/10;
        else
        cout<<num%10;
    }

    else if (n<2900) 
    {
        int k=n-189;
        int ptr=(k-1)/3;
        int num=100+ptr;

        int idx=(k-1)%3;
        if(idx==0)
        cout<<num/100;
        else if (idx==1)
        cout<<(num/10)%10;
        else if (idx==2)
        cout<<num%10;
    
    }

}
// 64 位输出请用 printf("%lld")