java - 在某些条件下最大化 GCD

Question

这是 hackerrank 中 HackWithInfy2019 给出的问题。从昨天开始我就被这个问题困扰了。

问题:

给定一个包含 N 个整数的数组。你必须找到一对 (i,j)最大化 GCD(a[i],a[j])+(j - i)和 1<=i

约束是:

2<= N <= 10^5

1<= a[i] <= 10^5

我用python试过这个问题

Answer 1

这里有一个可行的方法:

result = 0
min_i = array[1 ... 100000] initialized to 0
for j in [1, 2, ..., n]
    for d in divisors of a[j]
        let i = min_i[d]
        if i > 0
            result = max(result, d + j - i)
        else
            min_i[d] = j

这里，min_i[d] 对于每个 d 是最小的 i 使得 a[i] % d == 0。我们在内部循环中使用它，对于每个 d，找到数组中第一个元素，其 GCD 与 a[j] 至少为 d。当 j 是 gcd(a[i], a[j]) + j - i 最大的可能值之一时，当内部循环运行 d 等于所需的 GCD，result 将设置为正确答案。

小于或等于 100,000 的自然数的最大可能除数为 128(请参阅 here )。因此内循环最多运行 128 * 100,000 = 1280 万次。我想这可能会通过一些优化(尽管在 Python 中可能不会)。

(要迭代除数，请使用筛子预先计算 1 到 100000 之间每个整数的最小非平凡除数。)