POJ 2635 尷尬的密碼學家：大數取模與素數篩解法

問題描述

給大整數 K（最多 100 位）和整數 L（≤ 10⁶）。K 是兩個素數乘積。判斷較小素因子是否 < L。若是輸出 BAD p（p 為較小因子），否則 GOOD。

核心洞察

• K 過大無法直接因式分解，但只需檢查是否存在 < L 的素因子
• 枚舉所有 < L 的素數 p，檢查 K % p == 0
• 大數取模：逐位處理，rem = (rem * 10 + digit) % p

算法流程

1. 篩法預計算 10⁶ 以內所有素數（約 7.8 萬個）
2. 讀取 K 為字符串，L 為整數
3. 遍歷素數表中 < L 的素數 p：
   • 計算 K mod p
   • 若為 0，輸出 BAD p，結束
4. 若遍歷結束無因子，輸出 GOOD

大數取模優化：分塊處理

按 10⁴（萬進制）分塊，減少循環次數：

bool divisible(const string& K, int p) {
    long long rem = 0;
    for (char c : K) {
        rem = (rem * 10 + (c - '0')) % p;
    }
    return rem == 0;
}

// 萬進制版（需防溢出：rem < p ≤ 10⁶，rem*10000 < 10¹⁰，64位安全）
bool divisible_fast(const string& K, int p) {
    long long rem = 0;
    int len = K.length();
    for (int i = 0; i < len; i += 4) {
        int block = 0;
        for (int j = i; j < min(i+4, len); ++j)
            block = block * 10 + (K[j] - '0');
        rem = (rem * 10000 + block) % p;
    }
    return rem == 0;
}

完整代碼

#include 
using namespace std;

const int MAXL = 1000000;
vector primes;
bool is_composite[MAXL + 1];

void sieve() {
    for (int i = 2; i <= MAXL; ++i) {
        if (!is_composite[i]) primes.push_back(i);
        for (int p : primes) {
            if (i * p > MAXL) break;
            is_composite[i * p] = true;
            if (i % p == 0) break;
        }
    }
}

bool check(const string& K, int p) {
    long long rem = 0;
    for (char c : K) rem = (rem * 10 + c - '0') % p;
    return rem == 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    sieve();
    
    string K; int L;
    while (cin >> K >> L) {
        if (K == "0" && L == 0) break;
        bool found = false;
        for (int p : primes) {
            if (p >= L) break;
            if (check(K, p)) {
                cout << "BAD " << p << '\n';
                found = true;
                break;
            }
        }
        if (!found) cout << "GOOD\n";
    }
    return 0;
}

複雜度分析

• 篩法預處理：O(MAXL) ≈ 10⁶，一次性
• 單測試用例：O(π(L) × |K|) ≈ 7.8萬 × 100 = 7.8×10⁶ 操作，極快
• 空間：O(MAXL) 存素數表

避坑指南

• K 可能有前導零？題目說無標點空格，應無前導零
• L=0 或 K=0 為終止條件，不處理
• 素數表必須包含到 10⁶，線性篩最快
• 若 K 很短（如 < 18 位），可直接 stoll 轉數值再取模，更快