主題
題目連結：
題目意譯：
給定一個整數陣列 nums，回傳在 nums 中對於每一對索引值 0 ≦ i, j < nums.length 之 floor(nums[i] / nums[j]) 之值的總和。由於答案可能會太大，將其模 10 ^ 9 + 7 後再回傳。
floor() 函式將回傳上述除法中的整數部分。
（譯者注：這通常不是一般關於 floor() 的描述方式，但在本題中是夠用的。）
限制：
1 ≦ nums.length ≦ 10 ^ 5
1 ≦ nums[i] ≦ 10 ^ 5
範例測資：
範例 1：
輸入： nums = [2,5,9]
輸出： 10
解釋：
floor(2 / 5) = floor(2 / 9) = floor(5 / 9) = 0
floor(2 / 2) = floor(5 / 5) = floor(9 / 9) = 1
floor(5 / 2) = 2
floor(9 / 2) = 4
floor(9 / 5) = 1
我們計算陣列每一對索引值的除式之 floor 值並全數加總。
範例 2：
輸入： nums = [7,7,7,7,7,7,7]
輸出： 49
解題思維：
（令 n 為 nums 之長度而 M 為 nums 中最大值）
我們先觀察 floor(nums[i] / nums[j]) 的部分，並先忽略 nums 實際的內容而簡化成 floor(X / Y)。
因此如果我們先選擇固定 X 值，只變動 Y 值。則可以看到當 X < Y 時，floor(X / Y) 是 0，故直接考慮 X ≧ Y 的情況即可。而此時 Y 和 X 的關係可以寫成如下：
已知 f1 < f2 且兩者為 X 的某兩個「相鄰」因數（代表 f2 是最靠近 f1 的那一個因數）。
則當 Y = f1 + 1（含） ～ f2（含）時，floor(X / Y) = X / f2；而 Y = f1 時，floor(X / Y) = X / f1。
舉個例子，如 X = 12，則我們可以得到下列 Y 值（上排）與輸出值（下排）對應關係：
01, 02, 03, 04, 05, 06, 07, 08, 09, 10, 11, 12
12, 06, 04, 03, 02, 02, 01, 01, 01, 01, 01, 01
所以如果我們固定 X 值，極有可能要去因數分解 X。而單次分解 X 的時間複雜度將會是 O(√X)，所以整體的時間複雜度之下界至少會是 Ω(n × √M)（儘管還不知道其他部分怎麼處理，但對每個數字因數分解是免不了的了）。
感覺不理想？沒關係，我們還有另一個方向。
現在如果選擇固定 Y 值，只變動 X 值。如先前一致，我們只需考慮 X ≧ Y 的情況。而這次的關係式比較單純：
已知 d ≧ 1，則當 X = dY（含） ～ (d + 1)Y - 1（含）時，floor(X / Y) = d。
我們甚至可以把 X ≧ Y 的條件拿掉，直接將 d 改為 ≧ 0，上式也依舊成立。
一樣舉個例子，如 Y = 3，則我們可以得到下列 X 值（上排）與輸出值（下排）對應關係：
00, 01, 02, 03, 04, 05, 06, 07, 08, 09, ……
00, 00, 00, 01, 01, 01, 02, 02, 02, 03, ……
而如果 nums 中有 c 個 Y 值，則將輸出值乘以 c 即可（直接把 c 丟進去會太醜，故略過該表直接看下面的例子即可）。
因此現在假設 nums = [2, 2, 7, 3, 3, 3, 3]，則根據建立出來的 Y = 3 之表（如下）可以看到對於那一個 7 而言，floor(7 / 3) 會出現 4 次，因此總和為 2 × 4 = 8。
00, 01, 02, 03, 04, 05, 06, 07
00, 00, 00, 04, 04, 04, 08, 08
目前看起來好像沒有用。不過其他的 Y 值也可以建對應的表，如 Y = 2 或 7（承前例），可分別得到（記得下面每一個輸出值已經有乘以出現次數了）：
00, 01, 02, 03, 04, 05, 06, 07
00, 00, 02, 02, 04, 04, 06, 06
和
00, 01, 02, 03, 04, 05, 06, 07
00, 00, 00, 00, 00, 00, 00, 01
並且我們可以直接把輸出值的部分直接合併得到
00, 01, 02, 03, 04, 05, 06, 07
00, 00, 02, 06, 08, 08, 14, 15
所以直接掃過 nums = [2, 2, 7, 3, 3, 3, 3]，為每一個數字去上面查一次表格便可以得到每一個數字作為 X 值時，「所有數字」作為 Y 後的 floor(X / Y) 之總和。
可是這樣好像要掃過 0 ～ M 中的所有數字耶？而且這是對於單一一種 Y 值就要跑過所有數字一次，這樣的最糟時間複雜度下界不會是 Ω(nM) 嗎？
可以看到輸出值的變化發生於 Y 的倍數值 Y 、 2Y 、 3Y 等之位置（見上例）。所以我們直接把這些倍數值 dY 代表著整個 [dY, (d + 1)Y - 1] 的區間之輸出值。承一開始只有一個 Y = 3 的例子，其可得：
00, 01, 02, 03, 04, 05, 06, 07, 08, 09, ……
00, __, __, 01, __, __, 02, __, __, 03, ……
其中「_」只是佔位用的字元，代表著「空位」。不過這樣子不同 Y 值之間要合併就相當困難了，因為這代表著每一個表格的「空位」都可能要求一次。所以會跟一開始把整個表建出來一樣。
但是，我們還可以再進階一點。可以看到所有數字都出來的時候，各種 Y 值的表合併會很單純。所以我們的目標一樣是要得到
00, 01, 02, 03, 04, 05, 06, 07, 08, 09, ……
00, 00, 00, 01, 01, 01, 02, 02, 02, 03, ……
而實際上每個區間 [dY, (d + 1)Y - 1] 的輸出值可以看做是在 dY 之前（含）有多少個 Y 的非零倍數，也就是 d 個。
而且可以看到 dY + 1 從 dY 得到前面有 d 個的結論、dY + 2 從 dY + 1 得到 d 個的結論……而到 (d + 1)Y 時則從 (d + 1)Y - 1 得到 d 個並且因為自身是 Y 的倍數，因此數量會多 1 個。因此變成了 d + 1 個。
因此我們不如把每一個倍數值標出來，如承上例中：
00, 01, 02, 03, 04, 05, 06, 07, 08, 09, ……
00, 00, 00, 01, 00, 00, 01, 00, 00, 01, ……
其中只要是 Y 的倍數就會被標「01」，也就是說我們窮舉 d = 1 、 2 、 3 、……然後去標記對應的格子直到超過 M 為止便停下。
然後做一次前綴和（Prefix Sums，如這題）便可以得到目標表格：
00, 01, 02, 03, 04, 05, 06, 07, 08, 09, ……
00, 00, 00, 01, 01, 01, 02, 02, 02, 03, ……
所以回到 nums = [2, 2, 7, 3, 3, 3, 3] 的例子，然後為 2 、 3 和 7 各自建立標記倍數的表格（記得每一項一樣要乘以出現次數）分別為
00, 01, 02, 03, 04, 05, 06, 07
00, 00, 02, 00, 02, 00, 02, 00
、
00, 01, 02, 03, 04, 05, 06, 07
00, 00, 00, 04, 00, 00, 04, 00
和
00, 01, 02, 03, 04, 05, 06, 07
00, 00, 00, 00, 00, 00, 00, 01
而此時如果各自做前綴和再合併表格就會回到一開始的 Ω(nM) 了。
所以我們要先合併再做前綴和，而實際上這個「先合併」可以看做是在一開始就只使用一個表格，而各種 Y 值各自根據出現次數標記倍數（也就是將對應輸出值加上出現次數）。所以承上例，跑完所有 Y 值會得到
00, 01, 02, 03, 04, 05, 06, 07
00, 00, 02, 04, 02, 00, 06, 01
做完前綴和後便可以得到目標表格
00, 01, 02, 03, 04, 05, 06, 07
00, 00, 02, 06, 08, 08, 14, 15
有了目標表格就可以直接掃過 nums 去表格中取出對應輸出值並全數加總即是所求。
天啊，真是漫長的旅程不是嗎？那重點的時間複雜度呢？可以看到：
1. 配置記憶體給目標表格（以及拿來統計每一種 Y 值出現次數用的計數陣列）的時間是 O(M)。
2. 對於單一一個 Y 值而言，表格裡會被標記的格子數為 floor(M / Y) 個，為了簡化就直接寫為 M / Y（注意到 floor(M / Y) ≦ M / Y，因此不會少算）。
因此最糟就是 Y 值恰好 M 種，所以我們有
(M / 1) + (M / 2) + …… + (M / M)
將 M 提出來可得
M × ((1 / 1) + (1 / 2) + …… (1 / M))
可以看到後面的倒數總和，實際上就是調和級數（Harmonic Series，參見維基頁面）。而隨著 M 逐漸增大，後面的調和級數將會被 O(log(M)) 限制住。
因此所有 Y 值去標記的時間最多就是 O(M × log(M))。
3. 對上述表格做前綴和來產生目標表格。時間是 O(M)。
4. 掃過 nums 中每一個數字並在目標表格中尋找對應輸出值並全數加總。時間是 O(n)。
結合以上四點，可以得到時間複雜度為 O(n + M × log(M))。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
