arrays - 从两组中找到元素的所有组合，以使它们的几何均值落入第三组

Question

我有一个从1到n的整数。我将每个整数随机分配到三个集合中的一个每个整数都属于一个集合。因此，我需要计算所有元素的组合，使得A，B的几何平均值属于C。基本上A ∩ B = B ∩ C = C ∩ A = Ø。
我的解决方案是首先在一个(a,b)大小的数组上标记每个元素是否进入集合a、b或c。然后我循环遍历数组中属于a ∈ A, b ∈ B的所有元素。当我遇到一个元素时，我再次遍历属于a,b的所有元素。如果C，则添加sqrt(a*b) ∈ C作为一个可能的组合。然后对整个数组执行相同的操作，即n。
有没有可能的更好的解决方案？

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*k^2的搜索中，但是只有o（sqrt（n））这样的数字小于n。对于每对a，我们可以在O（1）中用你在问题中使用的表示来测试是否有一个好的c。
上述思想的一个关键部分是把a分解成s*t^2，即找到在a的因式分解中具有奇数幂的素数。
这可以通过一个预处理步骤来完成，这个步骤可以找到{1，2n}，使用稍加修饰的埃拉托森筛。这个修改后的版本不仅在遍历素数的倍数时将数字标记为“非素数”，而且还将当前素数追加到当前倍数的因子列表中。这个预处理步骤的时间复杂度是n*和{对于每个素数p＜n}（1／p）＝n*log（log（n））——详见this。
利用预处理的结果，即划分a的素数列表，我们可以在O（log（n））中找到那些具有奇数幂次的素数这是通过将a除以列表中的每个素数，直到它不再可被该素数整除来实现的如果我们做了奇数个除法，那么我们使用s中的当前素数。所有除法完成后，结果将等于1这是O（log（n））的复杂性，因为在最坏的情况下，我们总是将初始数除以2（最小素数），因此它最多需要对数2（a）步来达到值1。
主步骤的复杂性支配了预处理的复杂性，因此该方法的总体复杂度为O（n*qRT（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的搜索，但是只有O（sqrt（n））这样的数字小于n”。
让我们举个例子假设我们有一个n=10000的值，我们正在寻找一个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值（in o（sqrt（n））了。我们只需要考虑k=1，k=2，…，k=（int）sqrt（n/10）。k的值越大，b的值就越大。每个k值决定一个b值，我们需要验证。请注意，在验证这些b值中的一个时，应首先检查它是否确实在集合b中（可以在o（1）中完成），以及sqrt（a*b）是否在集合c中（也可以在o（1）中完成）。