从两个集合中找出元素的所有组合，使得它们的几何平均值落入第三个集合
Finding all combinations of elements from two sets such that their geometric mean falls into third set
我有一个从 1 到 n 的整数。我将每个整数随机分配到三个集合 A、B 和 C (A ∩ B = B ∩ C = C ∩ A = Ø) 中的一个。每个整数都属于一个集合。所以我需要计算所有元素组合 (a,b) 使得 a ∈ A, b ∈ 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).
是否有更优化的解决方案？
可以用比 O(n^2) 更好的复杂度来完成。此处草拟的解决方案是 O(n * sqrt(n) * log(n)).
主要思想如下：
- 让 (a, b, c) 成为一个很好的解决方案，即 一个带有 sqrt(a * b) = c 的解决方案。我们可以将 a 写成 a = s * t^2，其中 s 是 [=33 中具有奇数指数的素数的乘积=]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, b 我们可以在 O(1) 中测试是否有好的 c，使用您在问题中使用的表示法。
上述想法的一个关键部分是将 a 分解为 s * t^2，即 找到具有奇次幂的素数在 a 的因式分解中。
这可以使用预处理步骤来完成，该步骤使用略微修改的埃拉托色尼筛法找到 {1, 2, .. n} 中每个数字的质因数（但不是它们的幂）。这个修改后的版本不仅会在遍历素数的倍数时将数字标记为 "not prime"，还会将当前素数附加到当前倍数的因数列表中。这个预处理步骤的时间复杂度是 n * sum{for each prime p < n}(1/p) = n * log(log(n)) -- 详见this。
使用预处理的结果，即整除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 的因式分解的所有其他素数应该具有偶数指数。
在以下行展开："we can restrict our search for the number b to those of the form b = s * k^2, but there are only O(sqrt(n)) numbers like this smaller than 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)中完成。
我有一个从 1 到 n 的整数。我将每个整数随机分配到三个集合 A、B 和 C (A ∩ B = B ∩ C = C ∩ A = Ø) 中的一个。每个整数都属于一个集合。所以我需要计算所有元素组合 (a,b) 使得 a ∈ A, b ∈ 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).
是否有更优化的解决方案？
可以用比 O(n^2) 更好的复杂度来完成。此处草拟的解决方案是 O(n * sqrt(n) * log(n)).
主要思想如下：
- 让 (a, b, c) 成为一个很好的解决方案，即 一个带有 sqrt(a * b) = c 的解决方案。我们可以将 a 写成 a = s * t^2，其中 s 是 [=33 中具有奇数指数的素数的乘积=]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, b 我们可以在 O(1) 中测试是否有好的 c，使用您在问题中使用的表示法。
上述想法的一个关键部分是将 a 分解为 s * t^2，即 找到具有奇次幂的素数在 a 的因式分解中。
这可以使用预处理步骤来完成，该步骤使用略微修改的埃拉托色尼筛法找到 {1, 2, .. n} 中每个数字的质因数（但不是它们的幂）。这个修改后的版本不仅会在遍历素数的倍数时将数字标记为 "not prime"，还会将当前素数附加到当前倍数的因数列表中。这个预处理步骤的时间复杂度是 n * sum{for each prime p < n}(1/p) = n * log(log(n)) -- 详见this。
使用预处理的结果，即整除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 的因式分解的所有其他素数应该具有偶数指数。
在以下行展开："we can restrict our search for the number b to those of the form b = s * k^2, but there are only O(sqrt(n)) numbers like this smaller than 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)中完成。