0

我有一个从 1 到 的整数n。我将每个整数随机分配到三个集合A和( ) 之一。每个整数都属于一个集合。所以我需要计算所有元素的组合,这样和 的几何平均值属于。基本上。BCA ∩ B = B ∩ C = C ∩ A = Ø(a,b)a ∈ A, b ∈ Ba,bCsqrt(a*b) ∈ C

我的解决方案是首先在一个大小数组上标记n每个元素是否进入集合 A、B 或 C。然后我循环遍历数组以查找所有属于A. 当我遇到一个时,我再次遍历所有属于B. 如果array[sqrt(a*b)] == C,那么我添加(a, b, sqrt(a,b))一个可能的组合。然后我对整个数组做同样的事情,即O(n^2).

是否有更优化的解决方案?

4

1 回答 1

2

它可以以比 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. 对于像这样枚举的每一对ab我们可以使用您在问题中使用的表示在 O(1) 中测试是否存在好的c 。

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

这可以使用预处理步骤来完成,该步骤使用稍微修改的 Eratosthenes 筛子找到 {1, 2, .. n} 中每个数字的质因数(但不是它们的幂)。这个修改后的版本不仅会在迭代素数的倍数时将数字标记为“非素数”,而且还会将当前素数附加到当前倍数的因子列表中。此预处理步骤的时间复杂度为 n * sum{对于每个素数 p < n}(1/p) = n * log(log(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的形式,但只有 O(sqrt(n)) 像这样小于 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)。

于 2017-05-18T20:23:44.863 回答