UVA 1434 YAPTCHA：威爾遜定理與素數預處理 O(1) 查詢

題目轉述

計算 S(n) = ⌊( (3n+6)! + 1 ) / (3n+7) ⌋ - ⌊( (3n+6)! ) / (3n+7) ⌋ 對於 n = 1..N 的前綴和。多組測試，N ≤ 1,000,000。

數學化簡

• 設 p = 3n+7。若 p 為合數，則 p = ab (a,b>1)，a,b ≤ 3n+6，故 (3n+6)! ≡ 0 (mod p)，原式 = 0。
• 若 p 為素數，由威爾遜定理 (p-1)! ≡ -1 (mod p)，即 (3n+6)! ≡ -1 (mod p)，則 (3n+6)! + 1 ≡ 0 (mod p)，原式 = 1。

結論：第 n 項 = 1 當 3n+7 為素數，否則 0。

算法

1. 線性篩預計算 isPrime[3N+7] 至 3,000,007。
2. 前綴和 ans[i] = ans[i-1] + isPrime[3*i+7]。
3. 每查詢 O(1) 回答。

C++ 實作

#include 
using namespace std;
const int MAXN = 1000000;
const int LIM = 3*MAXN + 7;

bool isPrime[LIM+1];
int ans[MAXN+1];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    fill(isPrime, isPrime+LIM+1, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i*i <= LIM; ++i)
        if (isPrime[i])
            for (int j = i*i; j <= LIM; j += i)
                isPrime[j] = false;
    for (int i = 1; i <= MAXN; ++i)
        ans[i] = ans[i-1] + (isPrime[3*i+7] ? 1 : 0);
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        cout << ans[n] << '\n';
    }
    return 0;
}

複雜度

• 篩法：O(LIM log log LIM) ≈ 3e6，極快。
• 前綴和：O(N)。
• 查詢：O(1)。
• 記憶體：isPrime[3e6] ≈ 3MB，ans[1e6] ≈ 4MB。

關鍵點

1. 識別威爾遜定理應用場景：(p-1)! mod p。
2. 合數情況利用因子分解論證階乘含模數因子。
3. 預處理前綴和支援海量查詢。