题解 P2425 【小红帽的回文数】

· · 题解

我是蒟蒻，，，，，，

这道题嘛，第一眼以为是直接枚举；

然而，一看a的取值范围，显然不是裸暴力；

仔细一看题意，显然， a[i]+1 进制一定是使 a[i] 成为回文串的一种情况；

同时， a[i]-1 进制也一定是使 a[i] 成为回文串的一种情况(得到11)；

但题目要求最小的进制；

然后，考虑进制数的特殊性质，即这个进制数超过了 \sqrt{a[i]} 之后，

a[i]转换进制后得到的数一定是两位数(考虑当进制数为 a[i] 的情况可知)；

那么不妨设满足条件的两位数字均为j(由回文串可知)，那么一定有:

j*x+j=a[i];

-----------------------------------------------(其中 x 为进制数, x > \sqrt{a[i]} )-----------------------------------------------

j*(x+1)=a[i]; x=a[i]/j-1;

那么在 x > \sqrt{a[i]} 的情况下,只要找到一个j是a[i]的一个因数，

那么 a[i]/j-1 就是题目的一个答案

至于 x < \sqrt{a[i]} 的情况嘛，暴力跑一遍就好了，然后还有一两句特判，

贴上AC代码，，，各位大佬可以优化一下，，，

#include <cmath>
#define maxn 30
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
inline char GET_CHAR(){//读优卡常 
    static char buf[maxn],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,maxn,stdin),p1==p2)?EOF:*p1++;
}
template<class T>inline void read(T &x){//读优背一下就OK 
    x=0;int f=0;char ch=GET_CHAR();
    while(ch<'0'||ch>'9')  {f|=(ch=='-');ch=GET_CHAR();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=GET_CHAR();}x=f?-x:x;
}
bool f;
int T;
LL x;
LL re[1000];//注意long long 
inline bool judg(LL sta,LL n){
    f = true;
    int pos=0;
    while(n){
        //强迫症 
        //转进制 
        re[++pos]=
        n-n/sta*sta;
        n /= sta;
    }
    int l=pos>>1,r=((pos+1)>>1)+1;
    //等价于 l=pos/2,r=(pos+1)/2+1; 
    for(int i=l,j=r;i && j<=pos;--i,++j)
    //我跑的比较奇葩
    //从中间向两边扫 
        if(re[i]!=re[j]){f=false;break;}
    return f;
}
int main(){
    read(T);
    while(T--){
        x;LL y;
        read(x);//这就是a[i] 
        y=(LL)sqrt((double)x)+1;
        if(x==2){ puts("3");continue; }//特判 
        else if(x<=3){ puts("2");continue; }
        for(LL i=2LL;i<=y;++i)//x<√a[i]
            if(judg(i,x))
                { printf("%lld\n",i);break; }
        if(!f){
            for(LL i=x/y-1;i>=0;--i)//x>√a[i]
                if(x-x/i*i==0)
                    {printf("%lld\n",x/i-1);f=true;break;}
            if(!f) printf("%lld\n",x+1);//应该算最后防线吧，，， 
        }
    }
    return 0;
}