题目重点：化为 (x−N!)(y−N!)=(N!)²，用勒让德公式求 N! 的质因数指数并统计正整数有序解。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版把 (x,y) 作为有序对，精确返回 Python 任意精度整数；若无序对，答案变为 (D+1)/2。
- N≥1；N=0 的 0!=1 数学上也可处理，但题目只说正整数。
- 没有给模数，不能自作主张对 10^9+7 取模；N=10^6 的十进制结果很长，实际平台可能另有输出约束需核。
解题路线
- 令 M=N!。方程等价于 M(x+y)=xy，两边加 M² 并因式分解为 (x−M)(y−M)=M²。
- 正整数解必有 x>M、y>M，故 x−M 与 y−M 是 M² 的一对正因子；每个正因子 d 唯一对应有序解 (M+d,M+M²/d)。答案是 M² 的因数个数。
- 先筛出所有 p≤N。勒让德公式给 N! 中 p 的指数 e_p=⌊N/p⌋+⌊N/p²⌋+…；M² 中指数为 2e_p。
- 因数个数 D=∏(2e_p+1)。使用任意精度整数连乘；不需要显式构造巨大 M=N! 或枚举其因子。
手动走一遍
N=3，M=6，M²=36=2²×3²，因数数 D=(2+1)(2+1)=9。比如因子 d=1 对应 x=7、y=42；d=36 对应 x=42、y=7，训练版视为两对。无序时这两对合并，平方根因子 d=6 只计一次，共 (9+1)/2=5。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def ordered_reciprocal_pairs_factorial(n: int) -> int:
"""Exact count of ordered positive pairs 1/x + 1/y = 1/n!."""
if n < 1:
raise ValueError("n must be positive")
prime = bytearray(b"\x01") * (n + 1)
prime[0] = 0
if n >= 1:
prime[1] = 0
for p in range(2, int(n**0.5) + 1):
if prime[p]:
prime[p * p:n + 1:p] = b"\x00" * (((n - p * p) // p) + 1)
answer = 1
for p in range(2, n + 1):
if not prime[p]:
continue
exponent = 0
power = p
while power <= n:
exponent += n // power
power *= p
answer *= 2 * exponent + 1
return answer
if __name__ == "__main__":
assert ordered_reciprocal_pairs_factorial(1) == 1
assert ordered_reciprocal_pairs_factorial(3) == 9
复杂度
筛质数至 N 约 O(N log log N) 时间、O(N) byte 空间；逐质数计算指数需要 O(Σ log_p N) 次整数除法。答案是大整数，连乘成本取决于其位长，不能把任意精度乘法一律视为 O(1)。N≤10^6 可用筛与勒让德公式，直接枚举 x/y 不可行。
易错点与追问
容易失分的边界
- 把 N! 误写为 N，或把 M² 的质数指数仍用 e_p 而非 2e_p。
- 没有确认有序/无序对，答案可能相差近两倍。
- 使用固定 64 位整数存答案却没有题目给的模数。
- 显式算 N! 再试除每个因子，浪费巨大计算。
- 漏掉 x=y=2M 这一个对角线解。
继续深挖
- 如果只要模某整数的答案，连乘过程如何取模？
- 如果 x≤y，为什么答案是 (D+1)/2？
- 若右侧改为 1/K 而 K 给为质因数分解，算法怎样简化？
