从数组（X1，X2，Y）中查找三元组，使得X1 * X2 = Y ^ 2 [英] Find triplets from the array(X1,X2,Y), such that X1*X2=Y^2

问题描述

如何查找三胞胎，形成一个数组，

（X ₁ ，X ₂ ，Y），

使得

X ₁ * X ₂ = Y ²

X₁ * X₂ = Y²

结果和元素的范围是10 ⁵

There can't be any repetition in the result and the elements are in a range of 10⁵

我尝试通过采用所有组合来做到这一点，但是我想要一种有效的方法 ...

I have tried doing it, by taking all combinations, but I want an efficient approach ...

推荐答案

因为数字Y <== 100000最多具有6个不同的素数因子，每个Y ² 的因子对少于4064。平均而言，大约为100。

Because a number Y <= 100000 can have at most 6 distinct prime factors, each Y² will have less than 4064 factor pairs. On average, about 100.

这导致了O（N）算法...它的系数为x000，但它仍然比大型输入的O（N ² ）个解决方案：

That leads to an O(N) algorithm... It has a factor of x000 in it, but it will still be faster than the O(N²) solutions for large inputs:

1. 建立一个散列图，给出每个数字的出现频率数组（O（N））


2. 对于每个数字Y，将其完全分解，并为Y ² 生成每个可能的因子对。为了将Y分解，可以用小于316的素数进行试验除法。


3. 对于每一对，检查频率表以查看它们是否都除了Y之外也出现。请注意，Y是一个因数Y ² 中的一个，对于这个，您必须检查Y是否出现至少3次。

1. Build a hashmap that gives the frequency for each number in the array (O(N))
2. For each number Y, completely factorize it, and generate each possible pair of factors for Y². To factorize Y, trial division by primes less than 316 is fine.
3. For each pair, check the frequency table to see if they both appear in addition to Y. Note that Y is a factor of Y², and for this one you have to check to see if Y appears at least 3 times.

此外，您只需要检查哈希图的键，最多有100000个键。即使数组中每个< == 100000，也要检查少于700万个因子对。

Also, you only need to check the keys of the hashmap, and there are at most 100000 of those. Even if every number <= 100000 is in the array, there are less than 7M factor pairs to check.

这篇关于从数组（X1，X2，Y）中查找三元组，使得X1 * X2 = Y ^ 2的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！