计算低于N的数的倍数与O(1)复杂度的总和？

Question

我们给出两个数字M和N.我们需要计算N以下所有整数的总和,它们可以被M整除.

是否可以用O(1)复杂度来解决？

我知道这是一个非常简单的程序,可以通过循环轻松完成.但我想知道是否有可能应用某种公式或某种东西来直接计算可被M整除的数字之和.

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。