题意简述

给定一个整数 $n$，已知 $n = p \times q$，其中 $p, q$ 为不同质数，且 $1 < p < q < n$。 要求输出 $p$ 和 $q$。

数据范围：$6 \le n < 10^{30}$。

关键点

$n$ 是两个不同质数的乘积，即 $n$ 是半素数（semiprime）。

数据随机，意味着 $p$ 和 $q$ 的大小不会特别极端（不会一个很小一个很大）。

$n$ 最大 $10^{30}$，无法直接枚举到 $\sqrt{n}$。

常用方法

1. 试除法（小数据）

对于 $n < 10^{12}$，可以直接试除 $2$ 到 $\sqrt{n}$。

2. Pollard Rho（中等数据）

对于 $n < 10^{18}$，可以用 Pollard Rho 算法分解质因数。

3. 大数分解（大数据）

对于 $n$ 达到 $10^{30}$，需要更高效的方法，但题目说数据随机，所以 Pollard Rho 仍然可行，因为它的期望复杂度是 $O(n^{1/4})$，对于随机数据很快。

算法选择

由于 $n$ 是两个质数的乘积，我们只需要找到 $n$ 的一个非平凡因子 $p$，则 $q = n / p$。

Pollard Rho 算法步骤：

如果 $n$ 是偶数，直接返回 $2$。

随机选择一个 $x \in [2, n-1]$ 和 $c \in [1, n-1]$。

定义函数 $f(x) = (x^2 + c) \bmod n$。

用 Floyd 判环：$x = f(x)$, $y = f(f(y))$，计算 $\gcd(|x-y|, n)$。

如果 $\gcd > 1$ 且 $< n$，则找到因子；否则换 $c$ 重试。

实现细节

使用 __int128 进行大数乘法，避免溢出。

用 Miller-Rabin 检测质数，加速判断。

示例代码（框架）

cpp #include <bits/stdc++.h> using namespace std; using ll = long long; using i128 = __int128_t;

ll mod_mul(ll a, ll b, ll mod) { return (i128)a * b % mod; }

ll mod_pow(ll a, ll b, ll mod) { ll res = 1; while (b) { if (b & 1) res = mod_mul(res, a, mod); a = mod_mul(a, a, mod); b >>= 1; } return res; }

bool miller_rabin(ll n, int k = 10) { if (n < 2) return false; if (n == 2 || n == 3) return true; if (n % 2 == 0) return false; ll d = n - 1; int r = 0; while (d % 2 == 0) { d /= 2; r++; } for (int i = 0; i < k; i++) { ll a = 2 + rand() % (n - 3); ll x = mod_pow(a, d, n); if (x == 1 || x == n - 1) continue; for (int j = 1; j < r; j++) { x = mod_mul(x, x, n); if (x == n - 1) break; if (x == 1) return false; } if (x != n - 1) return false; } return true; }

ll pollard_rho(ll n) { if (n == 1) return 1; if (n % 2 == 0) return 2; ll x = rand() % (n - 2) + 2; ll y = x; ll c = rand() % (n - 1) + 1; ll d = 1; while (d == 1) { x = (mod_mul(x, x, n) + c) % n; y = (mod_mul(y, y, n) + c) % n; y = (mod_mul(y, y, n) + c) % n; d = __gcd(abs(x - y), n); if (d == n) return pollard_rho(n); } return d; }

int main() { ll n; cin >> n; ll p = pollard_rho(n); ll q = n / p; if (p > q) swap(p, q); cout << p << " " << q << endl; return 0; }

总结

使用 Pollard Rho 算法分解大数。

利用 __int128 处理大数乘法。

对于 $10^{30}$ 以内的随机半素数，Pollard Rho 在可接受时间内可分解。