HDU 1299 / SPOJ KPEQU：方程 1/x+1/y=1/n 及其階乘版解的個數計算

第一題：1/x + 1/y = 1/n

移項得 x = n + n²/k，其中 k = y - n > 0。
x 為整數 ⇔ k 整除 n²。
故解的個數 = n² 的**正約數個數**。
若 n = ∏ p_i^e_i，則 n² = ∏ p_i^(2e_i)，約數數 d(n²) = ∏ (2e_i + 1)。
無序對 (x,y) 數 = (d(n²) + 1) / 2。

第二題：1/x + 1/y = 1/n!

同理，解數 = d((n!)²) = ∏ (2*e_i + 1)，其中 e_i 為 n! 中質因數 p_i 的指數。
e_i = ∑_{k≥1} ⌊n/p_i^k⌋（Legendre 公式）。
結果極大，需**高精度乘法**（Java BigInteger 或 C++ 手寫大整數）。

C++ 核心代碼（第一題）

const int MAXN = 1e7;
int prime[MAXN], cnt; bool vis[MAXN];
void sieve() {
    for (int i=2;i 1) ans *= 3; // 剩餘質因子指數 1
    return (ans + 1) / 2;
}

Java 高精度版（第二題）

BigInteger ans = BigInteger.ONE;
for (int p : primes) if (p <= n) {
    int e = 0, m = n;
    while (m > 0) { m /= p; e += m; }
    ans = ans.multiply(BigInteger.valueOf(2L*e + 1));
}
System.out.println(ans);

複雜度

篩法 O(MAXN log log MAXN)，分解 O(√n / log n)。n ≤ 1e7 時極快。