You are given an integer array nums.
Your task is to find the number of pairs of non-empty subsequences (seq1, seq2) of nums that satisfy the following conditions:
The subsequences seq1 and seq2 are disjoint, meaning no index of nums is common between them.
The GCD of the elements of seq1 is equal to the GCD of the elements of seq2.
Return the total number of such pairs.
Since the answer may be very large, return it modulo 109 + 7.
Example 1:
Input: nums = [1,2,3,4]
Output: 10
Explanation:
The subsequence pairs which have the GCD of their elements equal to 1 are:
([1, 2, 3, 4], [1, 2, 3, 4])
([1, 2, 3, 4], [1, 2, 3, 4])
([1, 2, 3, 4], [1, 2, 3, 4])
([1, 2, 3, 4], [1, 2, 3, 4])
([1, 2, 3, 4], [1, 2, 3, 4])
([1, 2, 3, 4], [1, 2, 3, 4])
([1, 2, 3, 4], [1, 2, 3, 4])
([1, 2, 3, 4], [1, 2, 3, 4])
([1, 2, 3, 4], [1, 2, 3, 4])
([1, 2, 3, 4], [1, 2, 3, 4])
Example 2:
Input: nums = [10,20,30]
Output: 2
Explanation:
The subsequence pairs which have the GCD of their elements equal to 10 are:
([10, 20, 30], [10, 20, 30])
([10, 20, 30], [10, 20, 30])
Example 3:
Input: nums = [1,1,1,1]
Output: 50
Constraints:
1 <= nums.length <= 200
1 <= nums[i] <= 200
今天這題題目給我們一個一維正整數陣列 nums ，
題目希望我們從 nums 找出符合條件的兩子序列數量。
條件是這兩子序列(seq1, seq2)不得為空，且最大公因數相同。
這題我本來的想法是先把每個元素的公因數蒐集起來，
然後看看怎麼排列組合，但想一想還要維持子序列不得為空，
太麻煩了（＃。
今天這題是看人家解答的。
核心思想是透過 DP 循序找當前的最大公因數，
先求 K = max(nums)，因為最大公因數上界必定小於等於 K。
再者利用記憶化 DP 遞推，
在 nums 的每個元素都做三樣選擇：
- 加入 seq1
- 加入 seq2
- 跳過這個元素
這樣可以設計一個 mem 三維陣列做 DP，
第一個維度放 nums 的 index 、後面維度放當前 seq1, seq2 的分別的最大公因數。
因為要滿足兩子序列(seq1, seq2)不得為空，
所以要特別注意終止條件，seq1 及 seq2 的長度必須大於一個元素。
C++程式碼：
