查找所有商的总和

Question

给定两个数字M和N.令qi为i * N/M的整数部分。 qi从0到M-1的和是多少？ 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多，其余的，如i = qm + r，使得总量现在是

∑q ∑r [r*n/m] 

，其中来自0q款项k-1和r汇总来自0到m-1。现在到了关键的一步：因为n和m互质，为r = 0..m-1序列r*n是置换0, 1, 2, 3, ..., m-1模m。因此，序列[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)/2。因此，全部金额崩溃到k * (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。用欧几里德算法计算GCD可以做到relatively quickly，所以计算起来相当快。

Answer 2

它看起来像我试图总结0N/M + 1N/M + 2N/M + 3N/M ...（M-1）N/M。如果是这样，你有（0 + 1 + 2 + 3 ... +（M-1））N/M。由于（0 + 1 + 2 + 3 + ... +（M-1））是M *（M-1）/ 2，所以可以在O（1）中求解。 M的取消，你得到（M-1）N/2。