Codeforces Round #315 Div2 C. Primes or Palindromes? 素數表回文數預處理

問題描述

同 ID 3463，給定 p, q（A=p/q ≤ 42），求最大 n 使 π(n) ≤ A·rub(n)。

解法詳解

上界分析：質數密度 ~ 1/ln n，回文數密度 ~ √n/n = 1/√n。質數增長最終超過回文數。實測 n≈1.2×10⁶ 時 π(n) ≈ 42·rub(n)。因 A≤42，答案 ≤ 1.2×10⁶。

預處理步驟

1. 埃拉托斯特尼篩法求 is_prime[1..MAXN]
2. 前綴和 pi[i] = pi[i-1] + is_prime[i]
3. 回文判斷：轉字符串或數學反轉，前綴和 rub[i] = rub[i-1] + is_pal(i)

查找答案

從 MAXN 向下枚舉，找到第一個滿足 q * pi[i] <= p * rub[i] 的 i。若無則輸出 "Palindromic tree is better than splay tree"（但題目保證有解）。

代碼關鍵

const int MAXN = 1200000;
bool is_prime[MAXN+1];
int pi[MAXN+1], rub[MAXN+1];

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

int main() {
    // 篩法
    fill(is_prime+2, is_prime+MAXN+1, true);
    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) pi[i] = pi[i-1] + is_prime[i];
    for (int i=1; i<=MAXN; ++i) rub[i] = rub[i-1] + is_pal(i);
    
    int p, q; scanf("%d%d", &p, &q);
    for (int i = MAXN; i >= 1; --i)
        if (1LL * q * pi[i] <= 1LL * p * rub[i]) {
            printf("%d\n", i); return 0;
        }
    puts("Palindromic tree is better than splay tree");
}

注意事項

• 用 long long 防止乘法溢出
• MAXN 取 1.2e6 足夠（實際 1179858 為上界）
• 回文判斷 O(log n)，總預處理 O(N log N) 可接受