2025-05-25：最大公约数相等的子序列数量用go语言，给定一个整

摘要：2025-05-25：最大公约数相等的子序列数量。用go语言，给定一个整数数组 nums，需要计算满足以下条件的非空子序列对 (seq1, seq2) 的数量：

2025-05-25：最大公约数相等的子序列数量。用go语言，给定一个整数数组 nums，需要计算满足以下条件的非空子序列对 (seq1, seq2) 的数量：

1. seq1 和 seq2 是 nums 的两个非空子序列，且它们在原数组中的索引不重叠（即它们没有共同的元素下标）。2. seq1 中所有元素的最大公约数（GCD）与 seq2 中所有元素的最大公约数相等。
求满足上述条件的子序列对总数，并将结果对 1000000007 取模后返回。

输入： nums = [10,20,30]。

输出： 2。

解释：

元素 GCD 等于 10 的子序列对有：

([10, 20, 30]的10, [10, 20, 30])的20，30。

([10, 20, 30]的20，30, [10, 20, 30])的10。

题目来自力扣3336。

• 子序列对贡献 f[g1][g2]：对于所有可能的 g1 和 g2，计算满足 gcd(seq1) = g1 和 gcd(seq2) = g2 的子序列对的数量。• l 是 g1 和 g2 的最小公倍数（lcm(g1, g2)）。• c 是 nums 中 l 的倍数的数量（即同时是 g1 和 g2 的倍数的元素数量）。• c1 和 c2 分别是 nums 中 g1 和 g2 的倍数的数量。• 公式 (pow3[c] * pow2[c1 + c2 - 2*c] - pow2[c1] - pow2[c2] + 1) % mod 计算满足条件的子序列对数量：• pow3[c]：seq1 和 seq2 可以同时选择 l 的倍数的元素（每个元素可以出现在 seq1、seq2 或都不出现）。• pow2[c1 + c2 - 2*c]：seq1 和 seq2 只能选择非 l 倍数的 g1 或 g2 的倍数。• 减去 pow2[c1] 和 pow2[c2] 是为了排除 seq2 或 seq1 为空的情况。• +1 是为了修正减去的重复部分。• 使用 Möbius 函数 mu 进行容斥，避免重复计算。对于所有 i，遍历 j 和 k 的倍数，累加 mu[j] * mu[k] * f[j*i][k*i] 到答案中。• 最终答案需要对 mod 取模并调整为非负数。1. 预处理：• LCM 表：O(mx^2 * log(mx))（mx 是 nums 的最大值，这里是 200）。• 幂数组：O(mx)。• Möbius 函数：O(mx log(mx))（类似筛法）。2. 统计倍数数量：• 遍历 nums：O(n)。• 填充 cnt：O(mx log(mx))（每个数的倍数）。3. 计算 f[g1][g2]：• 双重循环：O(mx^2)。• 每次计算 f[g1][g2] 是 O(1)。4. 倍数容斥：• 三重循环：O(mx * (mx/i)^2)，最坏情况下是 O(mx^3)。

总时间复杂度：O(mx^3)，其中 mx = 200，因此实际计算量约为 200^3 = 8,000,000。

1. LCM 表：O(mx^2)。2. 幂数组和 Möbius 函数：O(mx)。3. 计数数组 cnt：O(mx)。4. f 数组：O(mx^2)。

总空间复杂度：O(mx^2)，即 O(200^2) = 40,000。

package mainimport ( "fmt" "slices")const mod = 1_000_000_007const mx = 201var lcms [mx][mx]intvar pow2, pow3, mu [mx]intfunc init { for i := 1; i