HDOJ 2303 The Embarrassed Cryptographer：大整數質因數檢測

題目大意

給定大整數 K（≤ 10^100）和下界 L（≤ 10^6）。K 是兩個質數的乘積。若 K 存在質因數 p < L，輸出 "BAD p"（p 為最小質因數）；否則輸出 "GOOD"。

解法思路

1. 預處理篩出所有 ≤ 10^6 的質數（約 78498 個）。
2. 對每個質數 p（從小到大），檢查 K 是否能被 p 整除。由於 K 極大，需用高精度取模：逐位處理字符串，rem = (rem*10 + digit) % p。
3. 若發現 p < L 且 K % p == 0，輸出 "BAD p" 並結束。
4. 若所有 p < L 都不整除，或質數表用完，輸出 "GOOD"。

關鍵優化

• 質數篩用線性篩或埃氏篩，O(N log log N) 預處理一次。
• 大數取模只需 O(len(K))，len ≤ 100，極快。
• 一旦找到第一個因子即可停止，因題目要求最小質因數。

完整代碼

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

const int MAXL = 1000000;
int isComp[MAXL+1];
int primes[MAXL/10];
int pcnt = 0;

void sieve() {
    for (int i = 2; i <= MAXL; i++) {
        if (!isComp[i]) primes[pcnt++] = i;
        for (int j = 0; j < pcnt && i*primes[j] <= MAXL; j++) {
            isComp[i*primes[j]] = 1;
            if (i % primes[j] == 0) break;
        }
    }
}

int main() {
    sieve();
    char K[110];
    int L;
    while (scanf("%s%d", K, &L) == 2) {
        if (strcmp(K, "0") == 0 && L == 0) break;
        int len = strlen(K);
        int ans = -1;
        for (int i = 0; i < pcnt; i++) {
            int p = primes[i];
            if (p >= L) break;
            int rem = 0;
            for (int j = 0; j < len; j++)
                rem = (rem * 10 + (K[j]-'0')) % p;
            if (rem == 0) {
                ans = p;
                break;
            }
        }
        if (ans == -1) puts("GOOD");
        else printf("BAD %d\n", ans);
    }
    return 0;
}

複雜度分析

• 預處理：O(MAXL) ≈ 10^6。
• 每測試案例：最多遍歷所有 < L 的質數，每個做 O(len(K)) 取模。最壞情況 L=10^6，質數約 7.8 萬，len=100，約 780 萬次操作，極快。
• 空間：O(MAXL)。

總結

本題核心是大整數取模與質數篩的結合。利用「K 只有兩個質因數」的性質，只要找到一個 < L 的質因數即可判定 BAD。線性篩預處理質數表，配合字符串模擬取模，代碼簡潔高效。