[洛谷P2425]小红帽的回文数

原题传送门

这道题需要枚举。如果直接枚举会$TLE$。

考虑进制的转换：对于$> x$的进制下，一定是回文数

回文长度$2$位：设每一位为$i$，进制为$x$，则该数为$i*x+i$。反之，如果$n=i*(x+1)$，则$x$进制下$n$为回文。但要满足$i<x$，所以$x>\sqrt{n}$时适用。

当$x \leq \sqrt{n}$时暴力判断，这样复杂度降为$O(T \sqrt{n})$。

 #include <bits/stdc++.h>

 using namespace std;

 #define re register

 #define rep(i, a, b) for (re int i = a; i <= b; ++i)

 #define repd(i, a, b) for (re int i = a; i >= b; --i)

 #define maxx(a, b) a = max(a, b);

 #define minn(a, b) a = min(a, b);

 #define LL long long

 #define INF (1 << 30)

 inline LL read() {

     LL w = ; int f = ; char c = getchar();

     while (!isdigit(c)) f = c == '-' ? - : f, c = getchar();

     while (isdigit(c)) w = (w << ) + (w << ) + (c ^ ''), c = getchar();

     return w * f;

 }

 int T, l[];

 LL n;

 int main() {

     T = read();

     rep(kase, , T) {

         n = read();

         if (n == ) printf("%d\n", );

         else if (n <= ) printf("%d\n", );

         else {

             register LL ans = INF;

             for (register int i = sqrt(n-); i; i--)

                 if (!(n - n / i * i)) {

                     ans = n / i - ;

                     break;

                 }

             register int range = sqrt(n), len;

             register bool flag;

             register LL x;

             for (register int i = ; i <= range; ++i) {

                 x = n;

                 len = ;

                 while (x) {

                     l[++len] = x - x / i * i;

                     x /= i;

                 }

                 flag = ;

                 for (register int j = ; j <= len / ; j++)

                     if (l[j] != l[len - j + ]) {

                         flag = ;

                         break;

                     }

                 if (flag) { ans = i; break; }

             }

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

         }

     }

     return ;

 }

另外这道题比较卡常，需要一定的优化。

巴特西

[洛谷P2425]小红帽的回文数

原题传送门

最新文章

热门文章