题意分析

给定多个大整数（最多20个，每个数的范围在2到2^54-1之间），要求对每个数进行质数判定。如果是质数，输出"Prime"；如果是合数，则输出其最小的质因数。

解题思路

1. 质数判定：使用Miller-Rabin素性测试算法，这是一个概率性测试，但通过选择合适的基，可以在2^64范围内实现确定性判断。

2. 因数分解：对于合数，使用Pollard's Rho算法进行因数分解。这是一种高效的随机化因数分解算法，特别适合大数的因数分解。

3. 最小质因数查找：分解得到所有质因数后，找出其中最小的一个。

算法选择原因

• Miller-Rabin：相比简单的试除法，它能以更高的效率处理大数质数判定。
• Pollard's Rho：对于大数分解，比试除法快得多，平均时间复杂度为O(n^{1/4})。
• 递归分解：实现简单直观，配合Pollard's Rho算法能有效分解大数。

标程代码

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

typedef long long Long;  // 使用 long long 确保足够大的范围

vector<Long> factors;

Long gcd(Long a, Long b) {
    while (b != 0) {
        Long t = b;
        b = a % b;
        a = t;
    }
    return a;
}

Long mul_mod(Long a, Long b, Long mod) {
    Long res = 0;
    a %= mod;
    while (b > 0) {
        if (b & 1) res = (res + a) % mod;
        a = (a * 2) % mod;
        b >>= 1;
    }
    return res;
}

Long pow_mod(Long x, Long n, Long mod) {
    Long res = 1;
    x %= mod;
    while (n > 0) {
        if (n & 1) 
            res = mul_mod(res, x, mod);
        x = mul_mod(x, x, mod);
        n >>= 1;
    }
    return res;
}

bool is_prime(Long n) {
    if (n < 2) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0) return false;

    Long d = n - 1;
    int s = 0;
    while (d % 2 == 0) {
        d /= 2;
        s++;
    }

    const Long bases[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
    
    for (int i = 0; i < 12 && bases[i] < n; ++i) {
        Long a = bases[i];
        Long x = pow_mod(a, d, n);
        if (x == 1 || x == n - 1) continue;
        
        bool composite = true;
        for (int j = 0; j < s - 1; ++j) {
            x = mul_mod(x, x, n);
            if (x == n - 1) {
                composite = false;
                break;
            }
        }
        if (composite) return false;
    }
    return true;
}

Long pollards_rho(Long n) {
    if (n % 2 == 0) return 2;
    if (n % 3 == 0) return 3;
    if (n % 5 == 0) return 5;

    srand(time(NULL));
    while (true) {
        Long c = rand() % (n - 1) + 1;
        Long x = rand() % (n - 2) + 2;
        Long y = x;
        Long d = 1;

        while (d == 1) {
            x = (mul_mod(x, x, n) + c) % n;  // 修复了这里缺少的右括号
            y = (mul_mod(y, y, n) + c) % n;
            y = (mul_mod(y, y, n) + c) % n;
            d = gcd((x > y) ? x - y : y - x, n);
        }
        if (d != n) return d;
    }
}

void factorize(Long n) {
    if (n == 1) return;
    if (is_prime(n)) {
        factors.push_back(n);
        return;
    }
    Long d = pollards_rho(n);
    factorize(d);
    factorize(n / d);
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        Long n;
        cin >> n;
        
        if (n < 1) {
            cout << "Invalid input\n";
            continue;
        }
        
        if (n == 1) {
            cout << "1\n";
            continue;
        }
        
        if (is_prime(n)) {
            cout << "Prime\n";
            continue;
        }

        factors.clear();
        factorize(n);
        
        if (factors.empty()) {
            cout << "1\n";
        } else {
            Long min_factor = *min_element(factors.begin(), factors.end());
            cout << min_factor << endl;
        }
    }

    return 0;
}

代码解释

1. mul_mod：实现快速模乘，防止大数相乘溢出
2. pow_mod：快速幂算法，高效计算模幂
3. is_prime：Miller-Rabin实现，使用特定基组确保确定性
4. pollards_rho：随机化因数分解算法
5. factorize：递归分解质因数
6. main：处理输入输出，整合各功能模块

该解决方案高效可靠，能够正确处理题目给定范围内的大整数质数判定和因数分解问题。