2

我想计算 [1,x] 范围内 n 的互质数。我曾尝试使用 euler phi 函数，但它给出了 [1,n]。任何人都可以建议修改 euler phi 或任何其他方法来做到这一点？我使用了 phi(n) = n* (1-(1/p)) 的乘积，其中 p 是 n 的质因子。

4

1 回答 1

2

您可以使用包含-排除原则

找到 N 的唯一素数（它们不能超过 10-12，考虑到 N 和 X <=10^10）。

现在你可以通过除法找到 <=x 并且可以被 'y' 整除的数字的数量。为 y 尝试所有 n 因子的组合（在最坏的情况下，你只会得到 2^10 (1024)）。现在使用包含排除来找到小于 x 的 n 的互质数。

这个想法是，如果一个数不是 n 的互质数，那么它将至少有一个与 n 共同的质数因子。

对于我们的示例，让我们考虑 X=35 和 N=30

  1. 首先找到数字的唯一质因数。（他们的数量不得大于 10-12）。N 的唯一素数因子 ={2,3,5}。

  2. 求每个因子PAIR的乘积。{2x3​​、2x5、3x5 或 6、10、15}。

  3. 求每个因子TRIPLET的乘积：{ 2x3x5 或 30}。

  4. 重复直到所有因素相乘：{N=30 并且不需要更多步骤}。

  5. 求 X 的总和除以步骤 1 中的每个因子：{X=35: (35/2)+(35/3)+(35/5) = (17+11+7)=35}

  6. 求 X 的总和除以第 2 步中的每个数字：{X=35: 35/65+3+2=10}

  7. 求 X 的总和除以第 3 步中的每个数字：{X=35:1}

  8. 重复直到第 4 步的所有结果都被吸收：{x=35 no more steps are required}

  9. 在 [1..X] = X - step5 + step6 - step7 等范围内的 N 的共素数。{N=30, X=35 由 35 - 35 + 10 - 1 = 9} 给出。

对于 N=30，X=60，您将拥有：

60 - (60/2 + 60/3 + 60/5) + (60/6 + 60/10+ 60/15) - (60/30) = 60 - (30+20+12) + (10+6 +4) - 2 = 60 -62 + 20 - 2 = 16。

假设 X = 10。N = 6 = 2 * 3。

我们有数字 {1, 2, 3, ..., 10}。

去掉 2 的所有倍数。得到：{1, 3, 5, 7, 9}。

删除所有 3 的倍数。您得到：{1, 5, 7}。

我们如何有效地计算这个？试着回答这个问题：[1, X] 中有多少个数可以被 p 整除？是楼层（X/p），对吧？即p, 2p, ..., kp，其中kp <= X。所以，我们可以从X中减去Floor(X/p)，你会得到在[1]中与p互质的数的个数， X]。

在此示例中，有 10 个数字。能被 2 整除的数是 10/2，即 5。所以，10-5 = 5 个数与 2 互质。同样，有 10/3=3 个数是 3 的倍数。所以，我们可以说有 5-3=2 与 2 和 3 互质的数吗？不，因为你重复计算了！为什么？p = 2 和 3 的计数中包含了 6。所以我们必须通过添加 2 和 3 的倍数来解决这个问题。在 [1, 10] 中只有一个 2 和 3 的倍数，即 6。所以，加 1。也就是说，答案是 10 - 5 - 3 + 1 = 3，这是对的。

对此的概括就是包含与排除原则。对于每个 n，我们只是在找到它的质因数，我知道它肯定会小于 10 左右。这是使用埃拉托色尼筛法完成的，然后是素数分解。（由于 X < 10^9，一个数所拥有的最大素数因数较少。尝试找出前 10 个素数的乘积。它将是：6469693230，大约为 64*10^9。（i考虑最大限制为 10^10。这可以很容易地扩展到像 10^18 这样的大数字。）

我希望这有帮助 ！！

于 2013-06-15T08:17:22.913 回答