Leetcode 3336. Find the Number of Subsequences With Equal GCD

• Leetcode 3336. Find the Number of Subsequences With Equal GCD
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3336. Find the Number of Subsequences With Equal GCD

1. 解题思路

这一题没能自力搞定，挺伤心的，看大佬的代码之后发现思路上是一个非常暴力的动态规划，就是不断地考察每一个元素加入到第一个数组、第二个数组以及不做操作时，所有可能的两个数组的最大公约数pair的种类和数目变化。

然后考察最终所有非空且最大公约数相同的pair的个数即可。

2. 代码实现

给出python代码实现如下：

MOD = 10**9+7class Solution:def subsequencePairCount(self, nums: List[int]) -> int:dp = defaultdict(int)dp[(0, 0)] = 1ans = 0for num in nums:ndp = deepcopy(dp)for (gcd1, gcd2), cnt in list(dp.items()):_gcd = num if gcd1 == 0 else gcd(num, gcd1)ndp[(_gcd, gcd2)] = (cnt + ndp[(_gcd, gcd2)]) % MOD_gcd = num if gcd2 == 0 else gcd(num, gcd2)ndp[(gcd1, _gcd)] = (cnt + ndp[(gcd1, _gcd)]) % MODdp = ndpfor (gcd1, gcd2), cnt in dp.items():if gcd1 != 0 and gcd1 == gcd2:ans = (ans + cnt) % MODreturn ans

提交代码评测得到：耗时7264ms，占用内存23.9MB。