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+7

class Solution:
    def subsequencePairCount(self, nums: List[int]) -> int:
        dp = defaultdict(int)
        dp[(0, 0)] = 1
        ans = 0
        for 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)]) % MOD
                
            dp = ndp

        for (gcd1, gcd2), cnt in dp.items():
            if gcd1 != 0 and gcd1 == gcd2:
                ans = (ans + cnt) % MOD
        return ans

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