本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-13 08:30:29

打表题。

看题一眼发现好像 $n$ 不会很大，打个表，发现当 $n=2 \times 10^6$ 的时候回文数的个数 $\times 42$ 已经 $<$ 素数的个数了。

所以考虑直接预处理 $2 \times 10^6$ 以内的素数个数以及回文数的个数，然后判断即可。

这里由于是 $\pi(n) \le A \cdot rub(n)$，由 $A=\frac{p}{q}$，那么就可以转化成 $\pi(n) \cdot q \le p \cdot rub(n)$ 来避免除法。

#include <bits\/stdc++.h>

using namespace std;

int T;
int cnt[2000010], cnt1[2000010];

bool is(int u) {
	string s = to_string(u), t = s;

	reverse(t.begin(), t.end());

	return s == t;
}
void init() {
	for (int i = 1; i <= 2000000; ++i) cnt[i] = 1;
	cnt[0] = cnt[1] = 0;
	for (int i = 2; i <= 2000000; ++i) {
		if (cnt[i]) {
			for (int j = 2; i * j <= 2000000; ++j)
				cnt[i * j] = 0;
		}
	}

	for (int i = 1; i <= 2000000; ++i) cnt[i] += cnt[i - 1], cnt1[i] += cnt1[i - 1] + is(i);
}

int main() {
	init();
	int p, q; scanf("%d%d", &p, &q);

	for (int n = 2000000; n >= 0; --n) {
		if (cnt1[n] * p >= cnt[n] * q) {
			printf("%d\n", n);
			return 0;
		}
	}

	return 0;
}