我最近在招聘挑战中遇到了这个问题:
给定一个区间 [L, R] (1 <= L,R <= 10^5)，我们需要告诉 [L, R] 中每个 K 在区间 [L, R] 中 K 的互质数.
例如L = 3，R = 7
对于 K = 3，[3, 7] = 3 (4, 5, 7) 中的互质数
对于 K = 4，[3, 7] = 3 (3, 5, 7) 中的互质数
当 K = 5 时，[3, 7] 中的互质数 = 4 (3, 4, 6, 7)
...
通过我的方法，我找到 R 以内的质数，然后对于每个 K，通过其质因数，计算互质数的数量，但我需要比这更好、更有效的方法。提前致谢。
最佳答案
一种方法如下。
对于每个数字 K 执行以下步骤:
- 找到 K 的质因数(让我们将这个集合表示为 D)。
- 利用包含-排除原理来统计[L,R]区间内至少有D中一个数的倍数的数字。这个数字将代表非数字的个数与 K 互质。
- 您可以在this answer中查看有关此包含-排除方法的更多详细信息。 (我的)。
- 该问题涉及任意集合 D(不一定包含素数)——在我们的例子中，D 包含素数，因此可以在此处更直接地计算来自该答案的最小公倍数 (lcm)，作为当前子集中的数字。
- 最后，要找到与 K 互质的数量，请从 [L, R] 区间内的值总数中减去先前找到的数量。
备注:在步骤2中，我们可以类似地使用包含排除原理来直接计算与K互质的数字(不过，我觉得计算K的倍数更自然)组 D) 中的数字。这不再需要步骤 3。
关于algorithm - 每个数字的互质数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/58870869/