主題
題目連結(jié)：
題目意譯：
你被給定一個索引值從 0 開始且長度為 n 的整數(shù)陣列 nums。
一個位於索引值 i（其中 0 ≦ i ≦ n - 2）的「分割」如果滿足前 i + 1 個元素之乘積與剩餘元素之乘積是互質(zhì)的話，則該分割視為合法。
例如說，如果 nums = [2, 3, 3]，則位於索引值 i = 0 的分割是合法的，因為 2 和 9 互質(zhì)；而位於索引值 i = 1 的分割則不合法，因為 6 和 3 不互質(zhì)。同時位於 i = 2 的分割不合法，因為 i == n - 1。
回傳最小的索引值 i 使得對應(yīng)分割合法。如果不存在著這樣子的分割，則回傳 -1。
兩個數(shù)值 val1 和 val2 如果滿足 gcd(val1, val2) == 1 的話，則兩數(shù)互質(zhì)。其中 gcd(val1, val2) 是 val1 和 val2 的最大公因數(shù)（Greatest Common Divisor）。
限制：
n == nums.length
1 ≦ n ≦ 10 ^ 4
1 ≦ nums[i] ≦ 10 ^ 6
範例測資：
範例 1：
輸入： nums = [4,7,8,15,3,5]
輸出： 2
解釋： 上列表格表示了位於索引值 i 時的前 i + 1 個元素的乘積值、剩餘元素的乘積值以及它們的最大公因數(shù)。
唯一合法的分割是在索引值 2 出現(xiàn)。
範例 2：
輸入： nums = [4,7,15,8,3,5]
輸出： -1
解釋： 上列表格表示了位於索引值 i 時的前 i + 1 個元素的乘積值、剩餘元素的乘積值以及它們的最大公因數(shù)。
此例不存在合法分割。
解題思維：
可以看到直接算前綴和後綴的乘積會需要大數(shù)乘法（所以可能 Python 會比較吃香？這部分我不知道。我的直覺是依舊會超時），而這不甚理想。
不過因為題目要的是「互質(zhì)」，因此我們可以改存前綴和後綴的各自質(zhì)因數(shù)之次方值（如果不互質(zhì)，代表存在著某個質(zhì)因數(shù)，使得兩者的次方值都大於 0）。因此我們需要先建立質(zhì)數(shù)表還有把數(shù)字質(zhì)因數(shù)分解的方法，參見這題。
定義 P[i] 為前 i + 1 個數(shù)字的乘積、S[i] 為後 n - i - 1 個（即 P[i] 定義後的剩餘數(shù)字）之乘積。而我們可以看到實際上對於任意 i 值（0 ≦ i < n - 2）：
P[i + 1] = P[i] * nums[i]
S[i + 1] = S[i] / nums[i]
也就是說我們一開始求完 P[0] 和 S[0] 之後，便可以按照上面的方式往右依序求得 P[1] 、 S[1] 、 P[2] 、 S[2] 、……。
當(dāng)然，因為我們要存的是質(zhì)因數(shù)次方值，因此我們會需要質(zhì)因數(shù)分解 nums[i]。分解完後更動對應(yīng)的 P[i] 、 S[i] 各自的質(zhì)因數(shù)次方值來得到 P[i + 1] 和 S[i + 1] 的質(zhì)因數(shù)次方值。
不過如果我們每次修改完來比較每一種可能的質(zhì)因數(shù)來確認是不是互質(zhì)的話，總體時間複雜度會是 O(n × sqrt(M) × (M ÷ log(M)))，其中 M 為 nums 中的最大值、 sqrt(M) 為 M 的平方根（代表著質(zhì)因數(shù)分解之時間），而 M ÷ log(M) 代表著需要比較的質(zhì)數(shù)數(shù)量（漸進逼近）。依舊不甚理想。
而我們可以把這個檢查融入到質(zhì)因數(shù)分解的過程中來降低時間複雜度。我們只需要宣告一個變數(shù) C，代表著有多少質(zhì)因數(shù)滿足兩個乘積的次方值都大於 0。而在質(zhì)因數(shù)分解 nums[i]，每得到一個質(zhì)因數(shù)的次方值就去修改 P[i] 和 S[i] 的對應(yīng)質(zhì)因數(shù)次方值。而如果：
原本兩者的都大於 0，但在修改後 S[i] 變成 0。則 C 應(yīng)減去 1（因為少一個質(zhì)因數(shù)滿足條件了）；
原本 P[i] 的值是 0，但在修改後 P[i] 和 S[i] 的次方值都大於 0。則 C 應(yīng)加上 1。
因為 P[i] 的次方值只會上升、S[i] 的次方值只會下降（不變的次方值當(dāng)然不影響 C），所以這兩個條件足夠了。
如上我們從 P[i] 與 S[i] 藉由質(zhì)因數(shù)分解得到 P[i] 和 S[i] 的質(zhì)因數(shù)次方值之後，只要檢查 C 是不是 0 即可得到是否互質(zhì)。如果 C 是 0，代表互質(zhì)，因此此時的 i + 1 即是所求（只有 i == 0 時比較特別）。
如果全部的 i 值都掃過一遍沒得到互質(zhì)的乘積的話，則回傳 -1。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
