求第N个回文数 模板

备忘。

 /*看到n可以取到2*10^9.说明普通方法一个个暴力计算肯定会超时的，那打表呢？打表我们要先写个打表的代码，这里不提供。打完表观察数据，我们会发现数据其实是有规律的。完全不需要暴力的把所有数据打出来了！

 通过数据我们发现，第n个回文数的规律如下：

 1位的回文数有9个

 2位的回文数有9个

 3位的回文数有90个

 4位的回文数有90个

 5位的回文数有900个

 6位的回文数有900个

 原因是什么呢，如四位数的回文数个数，我们只看字符串的一半，从1001到9999，只看一半就是共有90个回文数。

 通过这样的规律，我们知道，只要数位增加2位，相应的该数位回文数就会是上位的10倍。

 编码过程就是，先算出这个回文数有几位，然后算该位数下最小的回文数与该回文数的距离（回文数以一半为基准算）

 时间复杂度几乎为O（1），而之前的循环判断回文数并记数的方法明显快。*/

 #include<iostream>

 #include<cstdio>

 using namespace std;

 typedef long long ll;

 ll findhw(ll index){

     ll res,cnt=,w=,num=,half=;

     while(){

         if(w>&&w%==)num*=;

         w++;

         if(cnt+num>=index)break;

         cnt+=num;

     }

     index=index-cnt-;

     for(int i=;i<(w-)/;i++)

         half*=;

     half+=index;

     res=half;

     if(w%==)half/=;

     while(half){

         res=res*+half%;

         half/=;

     }

     return res;

 }

 int main(){

     ll n;

     while(~scanf("%lld",&n))

         printf("%lld\n",findhw(n));

     return ;

 }

早就忘了当时写这个是干嘛了。