在给定范围内以O(1)的复杂度计算一个数的倍数数量？

Question

我们有三个数字，L、R 和 K。我们需要计算在 L 和 R 之间（包括两端）能被 K 整除的数的数量。

是否可能用 O(1) 的复杂度解决这个问题？

我知道这是一个非常简单的程序，可以轻松地使用循环完成。但我想知道是否可能应用某种公式或其他方法来直接知道在 L 和 R 之间能被 K 整除的数字的计数。

例如，count = (R - L + 1) / K 在一些情况下可能有效。

还有什么其他方法吗？

- Vijay Chavda

---

请不要在SO上使用链接，因为它们可能会在未来某个时候失效，导致问题变得无用。请在此处描述问题。 - shapiro yaacov

你的例子在某些情况下可以工作 - 你只需要检查边缘情况（例如 r % k = 0 或不是等等）。 - shapiro yaacov

这个标题非常误导，因为它描述了一个可能更难的问题。你想要计算在给定范围内某个数的倍数。 - j_random_hacker

@j_random_hacker，这是我从HackerEarth上获取问题时的解释。请查看https://www.hackerearth.com/problem/algorithm/count-divisors/。 - Vijay Chavda

好吧，他们简单地称之为“Count Divisors”，这比错误更不清楚，而您的标题“计算一个数的因子（或除数）的数量”则使陈述更清晰，也更清晰地说明了为什么它是错误的--它们没有计算任何特定数字的除数。 （例如，10的约数或因子是1、2、5和10。）因此，请修复您的标题，我就会取消-1的评分。 - j_random_hacker

@j_random_hacker，好的，我已经更改了标题。希望现在清楚了 :) - Vijay Chavda

Answer 1

这是您的解决方案。

 quo1=l/k;
 quo2=r/k;
 rem=l%k;
 if(rem==0)
 {
   count=quo2-quo1+1;
 }
 else
 {
    count=quo2-quo1;
  }   

- Vatsal Prakash

---

假设l、r和k都是自然数，你可以使用r/k - (l-1)/k来代替。 - Mike Koltsov

很酷，这似乎更简单了。 - Vijay Chavda