如何使用O(1)的时间复杂度计算小于N的某个数的倍数之和？

Question

我们有两个数字M和N。我们需要计算所有小于N的、可以被M整除的整数的总和。

是否有可能用O(1)复杂度解决它？

我知道这是一个非常简单的程序，可以很容易地使用循环来完成。但我想知道是否有可能应用某种公式或其他方法直接计算小于N且可被M整除的数字的总和。

- VatsalSura

---

你为什么认为这是可能的呢？换句话说，你只是放弃了一个要求；但我们希望你向我们展示你尝试解决问题的努力。 - GhostCat

如果我们将数字N除以M，那么我们得到的是小于N且可被M整除的数字总数。因此，所有数字都将按照M的进度进行。我不太擅长数学，所以在这里询问。如果有人能指导我正确的方向，那真的会很有帮助。 - VatsalSura

这就是我们两个人所做的。两个答案都没有帮助吗？ - Bathsheba

是的，这是正确的。谢谢大家。 - VatsalSura

Answer 1

的确有一个O(1)的解决方案：

首先利用整数算术计算n = N / M，n是等差数列的项数，其首项和公差均为M。

因此求和公式（来自等差数列的公式）为

n * (1 + n) * M / 2

例如，考虑N = 23，M = 5。您要求的是5 + 10 + 15 + 20，即50。闭合形式的解法计算结果为4 * 5 * 5 / 2，也是50。

- Bathsheba

---

好的，那么再来点更难的，假设我们有两个数字m1和m2（假设在之前的例子中M=5，M2=3，N=23，并且我们想要仅计算15一次），那么我们可以轻松地添加三的倍数、五的倍数并减去15的倍数，但是如果我们有M1、M2、M3...M100等呢？ - Spyros Mourelatos

Answer 2

L:=floor(M/N)

M + 2*M + 3*M + ... + L*M 

= M (1+2+3+4+...+L)

这可以通过 维基百科求和 来解决。

= M*(L*(L+1)/2)

这可以在O(1)的时间复杂度内计算

- MrSmith42