algorithm - すべての商の合計を求める

Question

2つの数MとNが与えられます。qiをi*N/Mの整数部分とします。0からM-1までのiに対する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と余りに分割できるi = qm + rので、合計は次のようになります。

∑q ∑r [r*n/m]

ここで、からのq合計とから0へk-1のr合計。ここで重要なステップがあります。とは互いに素であるため、のシーケンスはmodmの順列です。したがって、シーケンスは、などの順列です。したがって、合計はに崩壊します。0m-1nmr*nr = 0..m-10, 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です。GCDの計算は、ユークリッドのアルゴリズムを使用して比較的迅速に実行できるため、計算はかなり高速になります。

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が得られます。