自动搬运

查看原文

来自洛谷，原作者为

	暮天闻角 **

搬运于2025-08-24 21:37:34，当前版本为作者最后更新于2018-02-10 18:39:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我是蒟蒻，，，，，，

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

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

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

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

但题目要求最小的进制；

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

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

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

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

那么在 $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;
}