大小>=2的所有子数组中的最大GCD

Question

给定一个数组，编写一个程序以在大小的所有子数组中找到最大 gcd

我的代码：

from fractions import gcd
from functools import reduce
def GCD(arr):
   x = reduce(gcd, arr)
   return x
t = int(input())
for T in range(0, t):
   n = int(input())
   arr = list(map(int, input().split()))
   gcdd = -1
   for i in range(n):
      for j in range(i+2, n):
         gcdd = max(gcdd, GCD(arr[i:j]))
print(gcdd)

它是O（N^2），还能再优化吗？

Answer 1

我认为max（GCD（子阵列大小

因为

假设有一个数组 a，b，c，d

那么GCD(a，b，c) = GCD(GCD(a，b)，c)

平均GCD(a，b，c)

意味着没有必要计算大小大于2的GCD，如果你增加子数组的大小，GCD保持恒定或减少。没有情况，如果你增加大小，那么GCd增加。

计算大小为 2 的子数组的 GCD 是 O（2*N），它几乎等于 O（N）。

我想你明白我想说什么。