回文数
定义
记字符串 \(w\) 的倒置为\(w^R\)。例如\((abcd)^R=dcba\)，\((abba)^R=abba\)。
对字符串 \(x\)，如果 \(x\) 满足\(x^R=x\)，则称之为回文；例如 abba 是一个回文，而 abed 不是。
一、判断回文数
法一
思路：
将原数字倒序，比较是否还和原数相同。
特点：
- 此方法只适用于判断回文数，不能判断回文字符串。
- 此方法可以去除回文数可能存在的前导0再进行判断。
代码：
#include <iostream>
using namespace std;
int main() {int n, t, s = 0;cin >> n;t = n; //拷贝一份nwhile (t) { //将t倒序存入s中，注意此方法会去除前导0s = 10 * s + t % 10;t /= 10;}s == n ? cout << "yes" : cout << "no";return 0;
}
法二
思路：
用字符串读入，双指针判断对称位置字符是否相同。
特点：
- 此方法适用于判断回文字符串。
- 此方法不可去除数字可能存在的前导0。
代码：
#include <iostream>
using namespace std;
int main() {string s;cin >> s;int i = 0, j = s.size() - 1;bool ok = true; //标记是否为回文串while (i <= j) {if (s[i] != s[j]) {ok = false;break;}i++, j--; //更新指针}ok ? cout << "yes" : cout << "no";return 0;
}
法三
思路：
利用string读入，使用<algorithm>库中的翻转函数reverse()将字符串直接翻转，进行比较。
特点：
代码简洁，可读性高，不易出错。
代码：
#include <iostream>
#include <algorithm>
using namespace std;
int main() {string s, t;cin >> s;t = s;reverse(t.begin(), t.end());s == t ? cout << "yes" : cout << "no";return 0;
}
二、回文数性质探究
1.回文数个数
思路：
为了表述的简洁性，这里我们定义一个函数 \(cnt(n)\) ，表示 n 位数的回文数总个数。再定义一个函数 \(num(n)\)，表示 n 位数的总个数。
根据回文数的定义，很显然任何 1 位数都是回文数，即 \(cnt(1) = 10\)。
回文数具有对称性，即关于中间的哪个数字镜面对称。那么我们就可以通过枚举左边一半的数字来构造一个回文数字。例如：左边一半是12，我们可以构造一个 3 位回文数121，我们也可以构造一个 4 位回文数1221。很显然，任意一个2位数字都可以构造成一个三位回文数和一个四位回文数，而任意一个三位回文数或四位回文数也唯一对应着一种构造方式。那么既然具有这种对应的关系，我们就可以确认：\(cnt(3)=cnt(4)=num(2)\)。
将以上方法进行拓展，我们就可以将一个回文数与一个自然数取得对应关系。也就是说，任意一个回文数我们都能找到它的唯一构造方式。
例如：12321是由123构造得来，99是由9构造得来，1001是由10构造得来...
顺理成章地，我们得到以下关系：
这样一来，我们把一个相对复杂的问题转化成了一个较简单的问题，即求 \(num(n)\)。这是数学上一种重要的思想：化归思想。
一个 n 位数的个数很容易得到，即 \(10^n-10^{n-1}\)，也就是 \(9*10^{n-1}\).
综上，我们得到了这个问题的答案：\(对于 \forall n\in N^*，均满足 cnt(2n) = cnt(2n-1) = 9*10^{n-1}\).
代码：
思路看懂了，代码就相当简单了。
#include <iostream>
#include <cmath>
using namespace std;
int main() {int n; //输入位数 ncin >> n;if (n & 1) n++; //如果n是奇数n >>= 1; //无论奇偶都要除以2cout << 9 * pow(10, n - 1);return 0;
}
2.回文素数
当回文数与质数结合在一起，会有什么奇妙的性质呢？我们来看看吧！
思路：
在这里我们还是分位数来讨论。
一位数都是回文数，那么显然只要满足质数即可。一位回文素数有 4 个：2 3 5 7.
两位数的回文数有9个，我们也很容易能看出来，除了11是质数外，其余的都是11的倍数，显然是合数。即：两位回文数有 1 个：11.
受此启发：我们不禁产生疑问，回文数具有如此优美的对称性，11的倍数也有一定的对称性，它们之间有没有什么联系呢？
答案是有的。
首先， 我们要有一定的前置知识，这属于小学奥数的范畴：如何判断一个数字是否为11的倍数：将该数字的奇数位相加的和与偶数位的和做差，差是11的倍数，则原数是11的倍数，否则不是。
例如：1234， \((1+3)-(2+4)= -2\)，不是11的倍数，故1234不是11的倍数。
1089：\((1+8)-(0+9)=0\)，是11的倍数，故1089是11的倍数。
1221：\((1+2)-(2+1)=0\)，是11的倍数，故1221是11的倍数。
于是我们发现：除11外，任意偶数位的回文数，均位11的倍数，即合数。理由如下：
任意偶数位回文数形式为：\(abcd...xx...dcba\)，其奇数位的和为 \(a+c+...+x+...+d+b\)，偶数位的和为 \(b+d+...+x+...+c+a\)，二者均等同于 \(a+b+c+d+...+x\)，故差一定为0，即此回文数为11的倍数，为合数。
由此，我们探究出了1位和偶数位的回文数与素数的关系。至于其他位数的回文数与素数的关系，我们就只能逐个判断了。
例题：OpenJudge - 11:回文素数
总时间限制: 5000ms 内存限制: 65536kB
描述
一个数如果从左往右读和从右往左读数字是相同的，则称这个数是回文数，如121，1221，15651都是回文数。给定位数n，找出所有既是回文数又是素数的n位十进制数。（注：不考虑超过整型数范围的情况）。
输入
位数n,其中1<=n<=9。
输出
第一行输出满足条件的素数个数。 第二行按照从小到大的顺序输出所有满足条件的素数，两个数之间用一个空格区分。
样例输入
1
样例输出
4 2 3 5 7
代码：
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
void print(int x) {if (x == 1) {cout << 4 << endl << "2 3 5 7";return;}if (x == 2) {cout << 1 << endl << 11;return;}if (!(x & 1)) {cout << 0 << endl;return;}ll i, j;vector<ll> a; //保存素数int l = pow(10, x / 2);int r = pow(10, x / 2 + 1);for (i = l; i < r; i++) { //枚举所有ceil(x/2)位数if (!((i / l) & 1)) //小优化，如果最高位是偶数，即构造出来的回文数i += l; //是偶数，则其一定不是质数，那么直接跳过这些数ll t = i, p = i / 10;while (p) { //构造其对应的回文数tt = 10 * t + p % 10;p /= 10;}bool ok = true;for (j = 2; j <= t / j; j++) { //简单的判断素数if (t % j == 0) {ok = false;break;}}if (ok)a.push_back(t);}cout << a.size() << endl;for (auto it : res)cout << it << " ";
}
int main() {int n;cin >> n;print(n);return 0;
}
运行时长：394ms 占用内存：268kB 均远低于题目要求。