题解：CF568A Primes or Palindromes?

FiraCode · 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;
}