UVA 1434 YAPTCHA：威爾遜定理與質數篩解題詳解

題目大意

給定 n、k，求 S(n) = Σ_{i=1..n} [ (3i+7) 是質數 ? 1 : 0 ]。多組測資，n ≤ 10^6。

數學核心：威爾遜定理

威爾遜定理：p 為質數 ⟺ (p-1)! ≡ -1 (mod p)。
題目式子經推導可化為：(3k+7) 為質數時貢獻 1，否則 0。因此問題轉化為：預處理 3i+7 的質數性，前綴和查詢。

解題步驟

1. 最大 3n+7 ≤ 3,000,007，用埃氏篩預處理所有質數。
2. 建立 ans[i] = ans[i-1] + is_prime(3*i+7) 前綴和陣列。
3. 每組查詢 O(1) 輸出 ans[n]。

完整代碼

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAXN = 1e6;
int ans[MAXN + 5];
bool vis[MAXN * 4 + 5]; // 3*MAXN+7

void prime_sieve(int n) {
    memset(vis, 0, sizeof(vis));
    for (int i = 2; i <= n; i++) {
        if (vis[i]) continue;
        for (int j = 2 * i; j <= n; j += i) vis[j] = 1;
    }
}

int main() {
    prime_sieve(MAXN * 4);
    ans[1] = 0;
    for (int i = 2; i <= MAXN; i++)
        ans[i] = ans[i-1] + (vis[3*i + 7] ? 0 : 1);

    int cas, n;
    scanf("%d", &cas);
    while (cas--) {
        scanf("%d", &n);
        printf("%d\n", ans[n]);
    }
    return 0;
}

關鍵點總結

• 題目看似複雜數學式，實則為威爾遜定理直接應用。
• 篩法上限設 4*MAXN 保證覆蓋 3n+7。
• 前綴和技巧將多查詢降為 O(1)。
• vis[x] == 0 表示質數，注意邏輯取反。