Codeforces Round #315 (Div. 2) C. Primes or Palindromes? 解題詳解

問題描述

給定兩個整數 p 和 q，令 A = p/q（其中 A ≤ 42）。定義 π(n) 為不超過 n 的質數個數，rub(n) 為不超過 n 的回文數個數。要求找到最大的 n 使得 π(n) ≤ A · rub(n) 成立。

核心觀察

題目關鍵在於發現質數的增長速度最終會超過回文數的增長速度。經過分析可知，當 n 大約達到 150 萬時，π(n) 約為 rub(n) 的 42 倍。由於 A ≤ 42，因此答案一定存在於 150 萬以內，且不可能出現「無解」的情況。

解題思路

1. 預處理質數計數：使用埃拉托斯特尼篩法預先計算 200 萬以內每個數的質數前綴和 π(n)。
2. 預處理回文數計數：遍歷 1 到 200 萬，判斷每個數是否為回文數，構建 rub(n) 前綴和陣列。
3. 暴力枚舉答案：從大到小枚舉 n，檢查 q · π(n) ≤ p · rub(n) 是否成立，第一個滿足條件的即為答案。

複雜度分析

篩法預處理時間複雜度 O(N log log N)，回文判斷 O(N log N)，枚舉 O(N)。空間複雜度 O(N)。其中 N = 2,000,000，完全在時限內。

關鍵代碼片段

const int MAXN = 2000000;
int prime_cnt[MAXN + 1], palin_cnt[MAXN + 1];
bool is_prime[MAXN + 1];

void sieve() {
    fill(is_prime, is_prime + MAXN + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= MAXN; ++i)
        if (is_prime[i])
            for (int j = i * i; j <= MAXN; j += i)
                is_prime[j] = false;
    for (int i = 1; i <= MAXN; ++i)
        prime_cnt[i] = prime_cnt[i - 1] + is_prime[i];
}

bool is_palindrome(int x) {
    int orig = x, rev = 0;
    while (x) { rev = rev * 10 + x % 10; x /= 10; }
    return orig == rev;
}

void init_palindrome() {
    for (int i = 1; i <= MAXN; ++i)
        palin_cnt[i] = palin_cnt[i - 1] + is_palindrome(i);
}

總結

本題看似需要複雜的數論知識，實則通過觀察數據範圍和增長趨勢，轉化為簡單的預處理 + 暴力枚舉問題。關鍵在於發現答案上界較小（150 萬），使得 O(N) 解法可行。