A21373. 素数和回文数（num.cpp）
填空题
中等
知识点
题目描述
素数和回文数（num.cpp）
题目描述
圣诞节联欢活动上有一个找数游戏。定义：
质数（素数）：大于 1 的正整数，不能被除自身和 1 以外的任何正整数整除；
回文数：正整数的十进制表示无前置零，且从左到右与从右到左读相同；
f (n)：不大于 n 的质数个数；
g (n)：不大于 n 的回文数个数。给定系数 A = p/q（p、q 为正整数），找出最大的正整数 n，使得 f (n) ≤ A×g (n)。若不存在则输出 0。
输入描述
输入一行包含两个正整数 p 和 q（p, q ≤10²，p≤42），分别为 A 的分子和分母。
输出描述
输出满足条件的最大 n，若无则输出 0。
样例输入1
1 1样例输出1
40样例输入2
1 42样例输出2
1样例输入3
6 4样例输出3
172参考答案
#include <iostream>
#include <cstring>
usingnamespacestd;
constint MAX_N = 2000; // 题目范围下足够大的上限（根据样例3输出172，扩大到2000保证覆盖）
int prime[MAX_N], cnt; // 存储质数列表、质数计数
bool is_prime[MAX_N]; // 标记是否为质数
int f[MAX_N]; // f(n): 不大于n的质数个数
int g[MAX_N]; // g(n): 不大于n的回文数个数
// 线性筛法预处理质数及f(n)
void init_primes() {
memset(is_prime, true, sizeof(is_prime));
is_prime[0] = is_prime[1] = false;
cnt = 0;
f[0] = f[1] = 0; // 0和1没有质数
for (int i = 2; i < MAX_N; ++i) {
if (is_prime[i]) {
prime[cnt++] = i;
f[i] = f[i-1] + 1;
} else {
f[i] = f[i-1];
}
// 线性筛标记合数
for (int j = 0; j < cnt && i * prime[j] < MAX_N; ++j) {
is_prime[i * prime[j]] = false;
if (i % prime[j] == 0) break;
}
}
}
// 判断一个数是否是回文数
bool is_palindrome(int x) {
if (x < 0) returnfalse;
int original = x;
int reversed = 0;
while (x > 0) {
reversed = reversed * 10 + x % 10;
x /= 10;
}
return original == reversed;
}
// 预处理回文数计数g(n)
void init_palindromes() {
g[0] = 0; // 0不是正整数，不计入
for (int i = 1; i < MAX_N; ++i) {
g[i] = g[i-1] + (is_palindrome(i) ? 1 : 0);
}
}
int main() {
init_primes();
init_palindromes();
int p, q;
cin >> p >> q;
int ans = 0;
// 从大到小遍历，找第一个满足f(n)*q ≤ p*g(n)的n
for (int n = MAX_N - 1; n >= 1; --n) {
// 用乘法避免浮点数精度问题
if ((longlong)f[n] * q <= (longlong)p * g[n]) {
ans = n;
break;
}
}
cout << ans << endl;
return0;
}
上一题
下一题