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

1. seq1 和 seq2 是 nums 的两个非空子序列，且它们在原数组中的索引不重叠（即它们没有共同的元素下标）。

2. seq1 中所有元素的最大公约数（GCD）与 seq2 中所有元素的最大公约数相等。
   求满足上述条件的子序列对总数，并将结果对 1000000007 取模后返回。

1 <= nums.length <= 200。

1 <= nums[i] <= 200。

输入： 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。

解决思路

1. 预处理

• LCM 表：预先计算 lcms[i][j] 表示 i 和 j 的最小公倍数（LCM），用于后续计算。
• 幂数组：预先计算 pow2[i] 和 pow3[i]，分别表示 2^i 和 3^i 对 mod 取模的结果，用于快速计算子序列的数量。
• Möbius 函数：预先计算 mu[i]，用于倍数容斥（Möbius inversion）以消除重复计数。

2. 统计倍数数量

• 计数数组 cnt：cnt[i] 表示 nums 中 i 的倍数的个数。通过遍历 nums 并统计每个数的倍数，填充 cnt 数组。

3. 计算子序列对

• 子序列对贡献 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 是为了修正减去的重复部分。

4. 倍数容斥

• 使用 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。

Go完整代码如下：

package main

import (
	"fmt"
	"slices"
)

const mod = 1_000_000_007
const mx = 201

var lcms [mx][mx]int
var pow2, pow3, mu [mx]int

func init() {
	for i := 1; i < mx; i++ {
		for j := 1; j < mx; j++ {
			lcms[i][j] = lcm(i, j)
		}
	}

	pow2[0], pow3[0] = 1, 1
	for i := 1; i < mx; i++ {
		pow2[i] = pow2[i-1] * 2 % mod
		pow3[i] = pow3[i-1] * 3 % mod
	}

	mu[1] = 1
	for i := 1; i < mx; i++ {
		for j := i * 2; j < mx; j += i {
			mu[j] -= mu[i]
		}
	}
}

func subsequencePairCount(nums []int) int {
	m := slices.Max(nums)
	// cnt[i] 表示 nums 中的 i 的倍数的个数
	cnt := make([]int, m+1)
	for _, x := range nums {
		cnt[x]++
	}
	for i := 1; i <= m; i++ {
		for j := i * 2; j <= m; j += i {
			cnt[i] += cnt[j] // 统计 i 的倍数的个数
		}
	}

	f := make([][]int, m+1)
	for g1 := 1; g1 <= m; g1++ {
		f[g1] = make([]int, m+1)
		for g2 := 1; g2 <= m; g2++ {
			l := lcms[g1][g2]
			c := 0
			if l <= m {
				c = cnt[l]
			}
			c1, c2 := cnt[g1], cnt[g2]
			f[g1][g2] = (pow3[c]*pow2[c1+c2-c*2] - pow2[c1] - pow2[c2] + 1) % mod
		}
	}

	// 倍数容斥
	ans := 0
	for i := 1; i <= m; i++ {
		for j := 1; j <= m/i; j++ {
			for k := 1; k <= m/i; k++ {
				ans += mu[j] * mu[k] * f[j*i][k*i]
			}
		}
	}
	return (ans%mod + mod) % mod // 保证 ans 非负
}

func gcd(a, b int) int {
	for a != 0 {
		a, b = b%a, a
	}
	return b
}

func lcm(a, b int) int {
	return a / gcd(a, b) * b
}

func main() {
	nums := []int{10,20,30}
	result := subsequencePairCount(nums)
	fmt.Println(result)
}