最长满意连续子阵列

Question

A是一个数组，B是A中所有元素的质因数阶，< code>size(A)=N (1

 Input(condition):
     A={4,9,25,6}     B={2,3,5}       size(A)=N=4      size(B)=M=3
 Output:
     {4，9，25}
 Reason:
     the continuous subarray's accmulate must be a square number, so in A, there 6 subarraies,
    {4}           4=2^2
    {9}           9=3^2
    {25}          25=5^2
    {4,9}         4*9=6^2
    {9,25}        9*25=15^2
    {4,9,25}      4*9*25=30^2
    but we want find the longest one, that means the size of subarray must be bigest, so the result is {4,9,25}.

到目前为止，我还没有想过这个问题，所以没有什么成就，但是我保证我已经想了很久了，希望有帮助，谢谢！

Answer 1

这不是全部答案，但它应该让你继续前进：

如果每个质因数的精度为偶数倍，则累加为平方数。

因此，对于每个可能的子阵列，计算yeach素因子的出现次数。如果每个因子的出现次数为偶数，则子数组的累加为平方数。

优化提示：

对于优化的解决方案，将质因数分解存储为 32 位数字，其中 bit=1 表示奇数，bit=0 表示偶数，然后将它们 XOR 运算在一起。如果总数为 0，则累积是一个平方数。

Answer 2

我将在Klas Lindbäck的回答中添加一些细节，并提出一个可能的解决方案。

首先，我们将乘积累加到位置< code>i，并将质因数分解存储在数组< code>partialPrimes中。按照Klas lindbck的建议，该数组将只包含指数是偶数(0)还是奇数(1)作为位域。

因此，

此外，我们存储了给定分解的最大索引的映射。

int partialPrimes[N]
lastPartialPrimes := 0
maxPrime = new Map<int, int>
for i from 0 to N - 1
    int primes = calculatePrimeDecomposition(A[i], B)
    partialPrimes[i] = lastPartialPrimes xor primes
    lastPartialPrimes = primes
    maxPrime[primes] = i
next

素数分解可以通过连续除以给定的素数因子并对相应的位进行异或来找到。

现在，为了检查是否所有因子都有偶数指数(因此，如果数字是平方数)，我们可以简单地将分解与0进行比较。

为了得到部分产品的分解，我们可以在相应的指数上减去分解。因此，例如，为了计算乘积A[4]*A[5]*A[6]*A[17]的分解，我们可以只计算partialPrimes[7]-partialPrimes[3]（index at end-index before）。

因此，要找到乘积为平方数的范围，我们需要找到相等的partialPrimes：

int maxLength = -1
int start = -1, end = -1
for i from 0 to N - 1
    //check if this product is already a square number
    if(partialPrimes[i] == 0 && maxLength < i + 1) 
    {
        maxLength = i + 1
        start = 0
        end = i
    }
    //is there a equal decomposition?
    else if maxPrime.contains(partialPrimes[i])
    {
        int newEnd = maxPrime[partialPrimes[i]]
        int newStart = i + 1
        int newLength = newEnd - newStart + 1
        if(newLength > maxLength)
        {
            start = newStart
            end = newEnd
            maxLength = newLength
        }
    }
next

代码只是用来说明整体思路，可能包含小错误。

如果我们假设素因子分解需要< code>O(d)时间，那么这个算法的总时间复杂度是< code>O(n * d)