不多说,直接看代码,都在注释里
// 中心思想:
// * 1. 代入数据只想回文的一半和位数的变化
// * 例. 1001 和 101 都存的是10, 但是位数一个是4, 一个是3
// * 2. 安装只存一半的思想,进位时是从中心进位
// * 例. 1001 => 1111, 101 => 111
// * 例. 99 => 101, 999 => 1001
// * 3. 进位时存储的方式
// * 例. 偶数进位后是奇数位的情况 (实际数字:9999 | 存储数字:99 | 位数:4) => (实际数字:10001 | 存储数字:100 | 位数:5)
// * 例. 奇数进位后是偶数位的情况 (实际数字:99999 | 存储数字:999 | 位数:5) => (实际数字:100001 | 存储数字:100 | 位数:6)
// * 例. 虽然都是进位,但是进位后的数字奇数时存储数字会进一位,偶数时不会进位
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
// 回文结构体
struct hui {
int w; // 位数
int n; // 回文的一半 奇数是w/2+1位 偶数是w/2位 如 1001为10, 101还是为 10
};
// 双重循环判质数,基础算法,就不注释了
// 有人特判二的倍数,但是我觉得不必要,进循环第一个试的就是2,时间复杂度没差多少
bool isZ(int n) {
if(n <= 1) {
return false;
}
for(int i=2; i*i<=n; i++) {
if(n%i==0) {
return false;
}
}
return true;
}
// 获取参数x之后的第一个回文数
hui getFirst(int x) {
// 初始化
int a[10] = {}; // 存每一位的数组
hui t; // 要返回的回文数结构体
// log10求位数 注意!!! log10返回浮点数!!!
t.w = log10(x)+1;
// 考虑顺序地拆解每一位 例如: 10是[1, 0]不是[0, 1]
for(int i=1; i<=t.w; i++) {
a[t.w-i] = x%10;
x /= 10;
}
// 这里是重点!!!
// 开始之前,先解释一串表达式 t.w/2-1+(t.w&1)
// 这串表达式是找到回文的中心,偶数是靠前一点的中心
// 位数除以二是找到中心,减一是适配数组从0开始,(t.w&1)是用位运算判断奇偶,奇数就返回1,偶数返回0,可以带入几个数试试
int i, j;
// 开始
i = 0;
// 结尾
j = t.w - 1;
// 左右两边向中心走(什么双指针之类的
while(i<j) {
// 重点中的核心!!!
// 如果右边的回文数比左边的大就让左边进一
// 例如 23042 出来的是 23100 不是24042!
// 13出来的是20 不是33!
// 因为结构体只存回文的一半, 所以只搞好一半就行
if(a[i] < a[j]) {
a[t.w/2-1+(t.w&1)]++;
break;
}
i++;
j--;
}
// 搞好数组了就要存入结构体,例如 1001 存 10, 100001存 100,存一半 (10001也是存10但是它们结构体里位数不一样
t.n = 0;
for(i = 0; i<t.w/2+(t.w&1); i++) {
t.n *= 10;
t.n += a[i];
}
return t;
}
// 下一个回文数
// 这个函数就是找规律
void nextHui(hui& x) {
int y = x.n;
x.n++;
// 是否进位
// 看文章开头的中心思想
if(int(log10(x.n))+1 != int(log10(y))+1) {
if(x.w&1) {
x.n /= 10;
}
x.w++;
}
}
// 结构体转int
int toInt(hui x) {
int s = x.n;
int t = x.n;
if(x.w&1) {
t /= 10;
}
while(t!=0) {
s *= 10;
s += t%10;
t /= 10;
}
return s;
}
int main() {
int start, end;
cin >> start >> end;
hui x;
x = getFirst(start);
// 没到就枚举
while(toInt(x) <= end) {
// 判断质数
if(isZ(toInt(x))) {
cout << toInt(x) << endl;
}
// 下一个回文数
nextHui(x);
}
return 0;
}
真的写了很久,题目更是写了一天请帮忙点个赞,这对我帮助很大
[原创][luogu]P1217 回文质数 真·生成回文的方法的相关教程结束。
