主題
題目連結：
題目意譯：
我們有兩陣列 arr1 和 arr2，其中兩者一開始都是空的。你需要新增一些正整數(shù)到這兩個陣列使得以下條件全數(shù)成真：
arr1 包含 uniqueCnt1 個相異正整數(shù)，其中每個整數(shù)都不被 divisor1 整除。
arr2 包含 uniqueCnt2 個相異正整數(shù)，其中每個整數(shù)都不被 divisor2 整除。
沒有整數(shù)同時出現(xiàn)於 arr1 和 arr2 中。
給定 divisor1 、 divisor2 、 uniqueCnt1 和 uniqueCnt2，回傳在兩個陣列中最小可以出現(xiàn)的最大整數(shù)。
限制：
2 ≦ divisor1, divisor2 ≦ 10 ^ 5
1 ≦ uniqueCnt1, uniqueCnt2 < 10 ^ 9
2 ≦ uniqueCnt1 + uniqueCnt2 ≦ 10 ^ 9
範例測資：
範例 1：
輸入： divisor1 = 2, divisor2 = 7, uniqueCnt1 = 1, uniqueCnt2 = 3
輸出： 4
解釋：
我們可以將前 4 個自然數(shù)到 arr1 和 arr2 中。
（譯者注：自然數(shù)在資訊科學等領域時常包含 0，所以這邊其實不恰當。改寫成非負整數(shù)就沒問題了。）
arr1 = [1] 且 arr2 = [2,3,4]。
我們可以看到兩個陣列都滿足所有條件。
因為最大值為 4，因此將其回傳。
範例 2：
輸入： divisor1 = 3, divisor2 = 5, uniqueCnt1 = 2, uniqueCnt2 = 1
輸出： 3
解釋：
這邊 arr1 = [1,2] 且 arr2 = [3] 便可以滿足所有條件。
因為最大值為 3，因此將其回傳。
範例 3：
輸入： divisor1 = 2, divisor2 = 4, uniqueCnt1 = 8, uniqueCnt2 = 2
輸出： 15
解釋：
在此，最終的可能陣列可以是 arr1 = [1,3,5,7,9,11,13,15] 且 arr2 = [2,6]。
可以證明不可能得到一個更小的最大值並滿足所有條件。
解題思維：
對答案本身進行二分搜尋法（Binary Search）即可，如這題。
假設現(xiàn)在我們猜兩個陣列中的數(shù)字都不超過 M，那要怎麼檢查現(xiàn)在猜得太大還太小？可以看到我們能先檢查最基本的條件：
- 令 C1 = M - floor(M ÷ divisor1) 、 C2 = M - floor(M ÷ divisor2)，其中 floor() 對於下高斯函數(shù)。
- 可看到 C1 、 C2 代表著各自去掉 divisor1 和 divisor2 的倍數(shù)後 nums1 和 nums2 的候選數(shù)字（先別管同時出現(xiàn)在兩者之間的）。而如果 C1 < uniqueCnt1 或是 C2 < uniqueCnt2 則表示我們猜得太小了（數(shù)字根本不夠用）。
可以看到我們還沒考慮可以同時出現(xiàn)於兩個陣列的數(shù)字，因此可以從此著手：
- 接著再令 C = M - floor(M ÷ L)，其中 L 為 divisor1 和 divisor2 的最小公倍數(shù)（Least Common Multiple)。
- 此時可看到 C 值代表著不被 divisor1 或 divisor2 整除的那些數(shù)字之數(shù)量，也就代表著這裡面包含著可能同時出現(xiàn)於兩陣列之中的數(shù)字。而如果 C < uniqueCnt1 + uniqueCnt2，則代表數(shù)字又不夠用了（代表把只能用在單一陣列的數(shù)字分配完之後去用剩下的、可以出現(xiàn)於兩陣列中的數(shù)字後也不夠）。
因此只要過程中出現(xiàn)「數(shù)字不夠用」（根據上面的條件），就「猜大一點」；反之，我們可以試著「猜小一點」。基本上流程就跟一般二分搜尋法（Binary Search）一致了。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
