查找所有商的總和

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。