找出两组元素的所有组合，使其几何平均值落入第三组

Question

我有一个从1到n的整数。我将每个整数随机分配到三个集合中的一个A、B和C（A的B的B的C的C的=C的A的Ø的A的=Ø的）。每个整数确实属于一个集合。所以我需要计算所有的元素组合（a，b），使得a，b的几何均值，和a，b的几何均值属于C。基本上sqrt（a*b）的C。

我的解决方案是首先在大小为 n 的数组上标记每个元素是否进入集合 A、B 或 C。然后，我在数组中循环查找属于 A 的所有元素。当我遇到一个时，我再次遍历属于 B 的所有元素。如果array[sqrt（a*b）] == C，那么我添加（a，b，sqrt（a，b））作为一个可能的组合。然后我对整个数组执行相同的操作，即 O（n^2）。

有没有更优化的解决方案？

Answer 1

它可以以比 O（n^2） 更好的复杂性来完成。这里勾勒的解决方案是 O（n * sqrt（n） * log（n））。

主要想法如下:

• 设（a，b，c）是一个好的解，即sqrt（a*b）=c的解。我们可以将a写成a=s*t^2，其中s是在a的素分解中具有奇数指数的素数的乘积。可以保证a的剩余部分是一个完美的正方形。由于a*b是一个完美的正方形，那么b必须是s*k^2的形式。对于每个a（有O（n）个这样的数字），在从上面的分解中找到s之后（这可以在O（log（n）中完成，如下所述），我们可以将对数字b的搜索限制为b=s*k2的形式，但是只有O（sqrt（n））个这样小于n的数字。对于每个对a，b这样枚举，我们可以在O（1）中测试是否有一个好的c，使用您在问题中使用的表示法

上述想法的一个关键部分是将 a 分解为 s * t^2，即找到在 a 的因式分解中具有奇数幂的素数。

这可以使用预处理步骤来完成，该步骤使用稍微修改的埃拉托色尼筛子来查找{1,2，… n}中每个数字的素数因子（但不包括它们的幂）。这个修改版本不仅会在迭代素数的倍数时将一个数字标记为“非素数”，还会将当前素数附加到当前倍数的因子列表中。对于每个素数p，这个预处理步骤的时间复杂度是n*和{

使用预处理的结果，即划分a的素数列表，我们可以找到O（log（n））中具有奇数幂的素数。这是通过将a除以列表中的每个素数来实现的，直到它不再可被该素数整除。如果我们进行了奇数次除法，那么我们使用s中的当前素数。完成所有除法后，结果将等于1。这的复杂性为O（log（n）），因为在最坏的情况下，我们总是将初始数除以2（最小素数），因此最多需要log2（a）步才能达到值1。

主步骤的复杂度决定了预处理的复杂度，因此该方法的总体复杂度为O（n*sqrt（n）*log（n））。

备注：在分解a=s*t^2中，s是a中素数与奇指数的乘积，但其指数不用于s（即s只是这些素数与指数1的乘积）。只有在这种情况下，才能保证b的形式为s*k^2。事实上，由于a*b=c*c，右手边的素数分解仅使用偶数指数，因此，s中的所有素数也应出现在b中，具有奇数指数，而b分解中的所有其他素数应具有偶数指数。

扩展以下行：“我们可以将对数字 b 的搜索限制为形式 b = s * k^2 的搜索，但只有像这样小于 n 的 O（sqrt（n）） 数字”。

让我们考虑一个例子。假设我们有大约n = 10，000，我们正在寻找a = 360 = 2^3 * 3^2 * 5的解。a的因式分解中奇数指数的素数是2和5(因此s = 2 * 5；a = 10 * 6^2).

由于a*b是一个完全平方，这意味着a*b的素因式分解中的所有素数都有偶数指数。这意味着这两个素数（2和5）也需要出现在具有奇数指数的b的因式分解，而b的素因子分解中的其余指数需要是偶数。因此，b的形式为s*k^2=10*k^2。

所以我们证明了b = 10 * k ^ 2。这很有帮助，因为我们现在可以快速地枚举这个形式的所有b值(在O(sqrt(n))中)。我们只需要考虑k = 1，k = 2，...，k = (int)sqrt(n / 10)。较大的k值导致b值大于n。这些k值中的每一个都决定了一个b值，我们需要验证这一点。注意，当验证这些B值之一时，应该首先检查它是否确实在集合B中，这可以在O(1)中完成，以及sqrt(a * b)是否在集合C中，这也可以在O(1)中完成。