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

def Sn(n):
    if n>=1:
        S=((9*n-1)*(10**n)+1)//9
    elif n==0:
        return 0
    else:
        print("Fuck!!!!!!!!!!")
        return
    return S
find=int(input())
finded=1
while(True):
    if Sn(finded-1)< find and find <= Sn(finded):
        location=find-Sn(finded-1)-1
        order=location//finded
        loc2=location%finded
        Sstr=10**(finded-1)+order
        Sstr=str(Sstr)
        print(Sstr[loc2])

        break
    else:
        finded+=1

令数列a_n=9*n*(10**（n-1)）(对于n位数，其总占用字符数为 每个数字占用字符n 与 n位数的数量 9乘10的n-1次方 的乘积)

利用错位相减法，可求得数列前n项和Sn=((9*n-1)*(10**n)+1)//9，也就是前n位数总占用字符数

故可以依据此找到目标字符位置位于第n位数的区域，其满足Sn-1< 待查找字符的编号<=Sn

然后 （待查找字符的编号-Sn-1）就是待查找字符属于第n位数字符的编号

利用其为n位数，可以利用整除运算找到对应的n位数是哪个，以及利用模运算来找到其对应该n位数的哪个数字

其时间复杂度应该为O(n//Sn)