最远互质算法

Question

给定一个包含 n 个数字的数组，用 [2, 250] 范围内距离最远的互质数替换每个元素。例如，2 的最远互质数是 249，243 的最远互质数是 2。

谁能帮我用最复杂的算法解决这个问题？

Answer 1

由于数字范围很小，我会选择一些筛法。

for (int i = 2; i <= N; ++i)
{
    if (N % i == 0)
    {
        sieve[i] = 1;
        for (int j = 2; j * i <= 250; ++j)
        {
            sieve[i * j] = 1;
        }
    }
}

使用它之后，您将寻找 sieve[sm] 为 0 的最小值 sm 和最大值 lg其中 sieve[lg] 是 0。然后从中获取到N的距离最大的那个。这就是你的答案。

Sieve 的复杂度为 O(nloglogn)。找到最远的循环将是 O(n)。所以总体复杂度为 O(nloglogn)。

这背后的逻辑:

简单地说，我们标记的值不是这个特定数字 N 的互质值。

然后我们只是循环获取与给定数字互质的最小和最大数字。然后我们计算距离，然后取最大的作为答案。