题意分析

给定一系列测试用例，每个用例包含一个大整数$K（4 ≤ K ≤ 10¹⁰⁰）$和一个整数$L（2 ≤ L ≤ 10⁶）。K$是两个质数的乘积。需要判断 $K$ 是否存在严格小于 $L$ 的质因数： 如果存在，输出 "BAD" 并附带最小的质因数 如果不存在，输出 "GOOD"

解题思路

使用埃拉托斯特尼筛法预先生成所有小于等于 10⁶ 的质数。筛法原理是：从 2 开始，将每个质数的倍数标记为非质数，最终未被标记的数即为质数。存储这些质数在列表中供后续使用。使用字符串表示 K，通过逐位取模运算判断整除性。

标程

#include <iostream>
#include <vector>
#include <cstring>
#include <cmath>
using namespace std;

const int MAXN = 1000000;

vector<int> get_primes(int n) {
    vector<bool> is_prime(n + 1, true);
    vector<int> primes;
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
            if ((long long)i * i <= n) {
                for (int j = i * i; j <= n; j += i) {
                    is_prime[j] = false;
                }
            }
        }
    }
    return primes;
}

int main() {
    vector<int> primes = get_primes(MAXN);
    string K_str;
    int L;
    while (cin >> K_str >> L) {
        if (K_str == "0" && L == 0) break;
        
        // 检查K是否偶数
        if ((K_str.back() - '0') % 2 == 0) {
            if (2 < L) {
                cout << "BAD 2" << endl;
                continue;
            }
        }
        
        bool found = false;
        int min_factor = -1;
        
        // 只检查小于L的质数
        for (int i = 0; i < primes.size() && primes[i] < L; ++i) {
            int p = primes[i];
            int remainder = 0;
            
            // 快速模运算
            for (int j = 0; j < K_str.size(); ++j) {
                remainder = (remainder * 10 + (K_str[j] - '0')) % p;
            }
            
            if (remainder == 0) {
                found = true;
                min_factor = p;
                break;
            }
        }
        
        if (found) {
            cout << "BAD " << min_factor << endl;
        } else {
            cout << "GOOD" << endl;
        }
    }
    return 0;
}