竞赛编程问题：求满足条件的二元组(a,b)数量的高效算法问询（p,q,n≤1e10）

阿华AIGC实验室

2026-4-21

Hey there! 这个问题确实没法暴力枚举，毕竟p、q、n都到1e10了，得靠数论变形来简化问题。我来一步步帮你拆解：

首先先把原式变形，这是这类分式等式问题的常用技巧：

题目要求 $\frac{ab}{a+b} = c \leq n$，其中 $a \in [1,p], b \in [1,q]$，所有数都是正整数。

我们对等式两边取倒数，得到：
$$\frac{1}{a} + \frac{1}{b} = \frac{1}{c}$$

接下来引入最大公约数来拆分a和b：设 $d = \gcd(a,b)$，令 $a = d \cdot x$，$b = d \cdot y$，这里 $\gcd(x,y) = 1$（因为已经把最大公约数提出来了）。把这个代入上面的倒数等式：
$$\frac{1}{dx} + \frac{1}{dy} = \frac{1}{c} \implies \frac{x+y}{dxy} = \frac{1}{c} \implies c = \frac{dxy}{x+y}$$

因为x和y互质，所以x+y和x、y都互质（想想看：如果x+y和x有公约数k>1，那k也会整除y=(x+y)-x，这和x、y互质矛盾）。所以x+y必须能整除d，我们设 $d = k \cdot (x+y)$，其中k是正整数。把d代回去，就能得到a、b、c的表达式：

$a = k \cdot x \cdot (x+y)$
$b = k \cdot y \cdot (x+y)$
$c = k \cdot x \cdot y$

现在问题就转化成：枚举所有互质的正整数对(x,y)，计算满足以下三个条件的k的数量，再把所有数量加起来：

$k \cdot x(x+y) \leq p$ → k不能超过 $\lfloor \frac{p}{x(x+y)} \rfloor$
$k \cdot y(x+y) \leq q$ → k不能超过 $\lfloor \frac{q}{y(x+y)} \rfloor$
$k \cdot xy \leq n$ → k不能超过 $\lfloor \frac{n}{xy} \rfloor$

对于每个(x,y)，k的最大有效取值就是这三个值的最小值，记为 $k_{\text{max}}$。如果 $k_{\text{max}} \geq 1$，那这个(x,y)就贡献 $k_{\text{max}}$ 个有效二元组(a,b)；如果 $k_{\text{max}}$ 小于1，就没有贡献。

接下来是高效枚举的技巧

你可能会担心枚举所有(x,y)会超时，但其实我们可以找到枚举的上限：

因为k≥1，所以 $x(x+y) \leq p$ → $x^2 < x(x+y) \leq p$ → $x \leq \sqrt{p}$，同理 $y \leq \sqrt{q}$。另外 $xy \leq n$，所以x不能超过 $\frac{n}{y}$。综合下来，x的枚举上限是 $\lfloor \sqrt{p} \rfloor$，对于每个x，y的上限是 $\min\left( \lfloor \frac{p}{x} - x \rfloor, \lfloor \frac{n}{x} \rfloor, \lfloor \frac{\sqrt{x^2 + 4q} - x}{2} \rfloor \right)$（最后这个是解二次不等式 $y(x+y) \leq q$ 得到的）。如果这个上限小于1，就不用枚举这个x对应的y了。

另外，我们可以分情况处理避免重复或者简化计算：

x=y的情况：
因为x和y互质，所以只有x=y=1这一种可能。此时a=2k，b=2k，c=k。对应的条件是2k≤p、2k≤q、k≤n，所以k的最大值是 $\min\left( \lfloor \frac{p}{2} \rfloor, \lfloor \frac{q}{2} \rfloor, n \right)$。如果这个值≥1，就把它加到总数里，否则加0。
x≠y的情况：
这里可以分开枚举x<y和x>y的互质对，但更直接的方式是对每个x，枚举所有满足条件且与x互质的y，计算对应的k_max并累加。判断互质可以用gcd(x,y)函数，竞赛里一般都有内置的或者自己实现一个快速gcd。

优化思路：用莫比乌斯反演进一步提速

如果觉得枚举互质对还是有点慢，可以用莫比乌斯反演来简化求和：

定义F(d)为所有满足gcd(x,y)是d的倍数的(x,y)对应的k_max之和，f(d)为gcd(x,y)=d的(x,y)对应的k_max之和，那么根据莫比乌斯反演，$f(1) = \sum_{d=1}^{\sqrt{max(p,q,n)}} \mu(d) \cdot F(d)$，其中μ是莫比乌斯函数。
计算F(d)时，我们令x=dx'，y=dy'，那么条件就转化为针对p'=p/d²、q'=q/d²、n'=n/d²的问题，当d²>max(p,q,n)时F(d)=0，否则计算所有x',y'对应的k_max'之和即可。

不过对于1e5级别的枚举量来说，直接枚举互质对已经足够通过题目了，莫比乌斯反演算是进阶优化。