algorithm - 求所有商的总和

Question

给定两个数 M 和 N。令 qi 是 i*N/M 的整数部分。从 0 到 M-1 的 qi 的总和是多少。O(M) 是显而易见的方法。这可以在更短的时间内完成吗，如果存在一些更简单的简化表达式，可能是 O(1)？

Answer 1

有趣的问题。（这篇文章会让我希望我们在 SO 上有数学格式……）

我的方法是将问题写为

∑i floor(i*N/M) = ∑i i*N/M - ∑i [i*N/M]

其中[]是“小数部分”运算符（即 [1.3] = 0.3、[6] = 0 等）。

然后，前半部分很简单：它是一个正常的等差数列和乘以N/M，所以它总和为N*(M-1)/2。下半场处理起来比较棘手，但您会明白为什么将其与上半场分开至关重要。

让k = gcd(N, M). 然后，让n = N/k和m = M/k，所以后半部分是∑i [i*n/m]。至关重要的是n，m现在是相对优质的。总和i是从0到M-1 = km-1。我们可以拆分i为m和余数的倍数，as i = qm + r，所以现在的和是

∑q ∑r [r*n/m]

其中qsum from 0tok-1和rsums from 0to m-1。现在到了关键步骤：因为n和m是相对素数，所以r*nfor的序列r = 0..m-1是mod m的排列。因此，该序列是 的排列，所以。因此，整个总和折叠为。0, 1, 2, 3, ..., m-1 [r*n/m]0/m, 1/m, 2/m, ..., (m-1)/m∑r [r*n/m] = ∑r r/m = m*(m-1)/2/m = (m-1)/2k * (m-1)/2 = (km - k) / 2 = (M - k) / 2

最后，我们将两半合并：N*(M-1)/2 - (M-k)/2 = (NM - N - M + k)/2.

因此，所需的总和是(NM - N - M + gcd(N, M))/2。使用 Euclid 算法可以相对快速地计算 GCD ，因此计算起来相当快。

Answer 2

在我看来，您正在尝试将 0N/M + 1N/M + 2N/M + 3N/M ... (M-1)N/M 相加。如果是这样，你有 (0+1+2+3...+(M-1))N/M。你可以在 O(1) 中解决这个问题，因为 (0+1+2+3+...+(M-1)) 是 M*(M-1)/2。M 取消，你得到 (M-1)N/2。