• 时间复杂度：$O(logn)$

long long nthPalindrome(long long n)
{
    long long cnt=0,num=9;
    int x=0;
    while(true)
    {
        if(x>0&&x%2==0)num*=10;
        x++;
        if(cnt+num>n)break;
        cnt+=num;
    }
    n-=cnt;
    int h=1;
    for(int i=0;i<(x-1)/2;i++)h*=10;
    int half=h+n;
    long long res=half;
    if(x&1)half/=10;
    while(half)
    {
        res=res*10+half%10;
        half/=10;
    }
    return res;
}