P2425 小红帽的回文数

旧城等待， 2021-12-22 15:57 168阅读 0赞

# P2425 小红帽的回文数 #

暴力枚举转换进制这个是人都会。但是只有40pts。

其实有这么个规律：对于\\(x\\)，在\\(x+1\\)进制下肯定是回文数，之后也是，因为只有一位。所以只需要枚举到\\(x+1\\)为止。但是没什么用。

我们考虑优化其中一部分进制。

当进制小于\\(\\sqrt\{a\_i\}\\)时，会有很多位，而大于等于\\(\\sqrt\{a\_i\}\\)时只有两位。

两位还回文，那这两位数字都相同。设这个数字为\\(j\\)，进制为\\(b\\)，则有：

\\\[b \\times j + j=a\_i\\\]  
可以解出\\(b=\\frac\{a\_i\}\{j\}−1\\)，当\\(a\_i\\)能被\\(j\\)整除时就有解。

所以当进制小于\\(\\sqrt\{a\_i\}\\)时，复杂度为  
\\(O(\\sqrt\{a\_i\} \\log⁡ \\sqrt\{a\_i\})\\)，大于等于时为\\(O(\\sqrt\{a\_i\})\\)。

所以能过。

代码：

#include<cstdio> #include<cmath> #include<vector> #define ll long long const int maxn = 100005; ll vec[maxn], tot; ll m; bool check(ll a, ll b) { tot = 0; while(a) { vec[++tot] = a % b; a /= b; } ll i = 1, j = tot; while(i <= j) { if(vec[i] != vec[j]) return false; i++, j--; } return true; } ll read() { ll ans = 0, s = 1; char ch = getchar(); while(ch > '9' || ch < '0') { if(ch == '-') s = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') ans = ans * 10 + ch - '0', ch = getchar(); return s * ans; } int main() { m = read(); while(m--) { ll a = read(); ll lim = sqrt(a); bool flag = false; for(ll i = 2; i <= std::max(2ll, lim); i++) { if(check(a, i)) { printf("%lld\n", i); flag = true; break; } } if(flag) continue; for(ll i = a / lim; i; i--) { if(a % i == 0) { printf("%lld\n", a / i - 1); flag = true; break; } } if(flag) continue; printf("%lld\n", a + 1); } return 0; }

转载于:https://www.cnblogs.com/Garen-Wang/p/10959622.html

发表评论取消回复

表情：

评论列表（有 0 条评论，168人围观）

还没有评论，来说两句吧...

相关阅读

相关回文数

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。示例 1: 输入: 121 输出: true 示例 2:

你的名字/ 2023年07月24日 02:10/ 0 赞/ 45 阅读

相关回文数

include<stdio.h> int main() { int n,m,s=0,t; while(scanf("%

傷城~/ 2023年07月15日 09:20/ 0 赞/ 3 阅读

相关回文数

import java.util.Scanner; public class PalindromeTest { public sta

港控/mmm°/ 2022年12月20日 11:12/ 0 赞/ 166 阅读

相关回文数

题目：判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。示例 1: 输入: 121 输出: true 示例 2: 输

傷城~/ 2022年11月19日 09:50/ 0 赞/ 286 阅读

相关 Vijos P1304回文数

P1304回文数 [Accepted][] 标签： [NOIP提高组1999][NOIP_1999] \[显示标签\] 描述若一个数（首位不为零）从左向右

╰+攻爆jí腚メ/ 2022年08月21日 00:13/ 0 赞/ 151 阅读

相关回文数

【问题描述】当一个数从前往后写与从后往前写时相等，则该数被称为回文数，所有的个位数都是回文数。所有非回文数通过一系列的操作都可以匹配一个

快来打我*/ 2022年06月03日 01:49/ 0 赞/ 261 阅读

相关回文数

import java.util.Scanner; public class Main \{ public static void main(String\[\] arg

àì夳堔傛蜴生んèń/ 2022年04月05日 17:40/ 0 赞/ 278 阅读

相关 P2425 小红帽的回文数

P2425 小红帽的回文数暴力枚举转换进制这个是人都会。但是只有40pts。其实有这么个规律：对于\\(x\\)，在\\(x+1\\)进制下肯定是回文数，之后也是，

旧城等待，/ 2021年12月22日 15:57/ 0 赞/ 169 阅读

相关回文数

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。示例 1: 输入: 121 输出: true

短命女/ 2021年10月29日 12:00/ 0 赞/ 422 阅读

相关回文数

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。示例 1: 输入: 121 输出: true 示例 2: 输入: -12

一时失言乱红尘/ 2021年10月15日 03:43/ 0 赞/ 404 阅读