调试中...
困难
相关标签
相关企业
提示
给你一个整数数组 nums。
请你统计所有满足以下条件的 非空 对 (seq1, seq2) 的数量：
- 子序列
seq1和seq2不相交，意味着nums中 不存在 同时出现在两个序列中的下标。 seq1元素的 等于seq2元素的 GCD。
返回满足条件的子序列对的总数。
由于答案可能非常大，请返回其对 109 + 7 取余 的结果。
示例 1：
输入： nums = [1,2,3,4]
输出： 10
解释：
元素 GCD 等于 1 的子序列对有：
([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])
示例 2：
输入： nums = [10,20,30]
输出： 2
解释：
元素 GCD 等于 10 的子序列对有：
([10, 20, 30], [10, 20, 30])([10, 20, 30], [10, 20, 30])
示例 3：
输入： nums = [1,1,1,1]
输出： 50
提示：
1 <= nums.length <= 2001 <= nums[i] <= 200
通过次数
1.8K
提交次数
3.3K
通过率
55.3%
相关企业
提示 1
Use dynamic programming to store number of subsequences up till index
i with GCD g1 and g2.相似题目
评论 (0)
贡献者
© 2025 领扣网络（上海）有限公司
0 人在线
行 1，列 1