2023-08-22：请用go语言编写。给定一个长度为N的正数数组，还有一个正数K， 返回有多少子序列的最大公约数为K。 结果可

2023-08-22：请用go语言编写。给定一个长度为N的正数数组，还有一个正数K，

返回有多少子序列的最大公约数为K。

1

1

来自腾讯笔试。

来自左程云。

答案2023-08-22：

算法过程分步描述如下：

1.初始化数组 、 和 ，长度为 MAXN，全部初始值为 0。

2.读取数组长度 N 和正数数组 arr。

3.初始化变量 ii 为 0，用于遍历 arr。

4.设置 pow2[0] 为 1，表示 2^0。

5.遍历数组 arr，从 1 到 N：

a. 读取当前元素 v，即 arr[ii]。

b. 将 v 在 cnt 数组中的计数加 1。

c. 计算 pow2[i]：pow2[i] = (pow2[i-1] * 2) % mod。

6.从 MAXN-1 循环到 1：

a. 初始化 counts 为 0，用于统计具有因子 i 的元素个数。

b. 遍历 cnt 数组，从 i 开始，以 i 为步长，累加 cnt[j] mod mod 到 counts。

c. 计算 dp[i]：dp[i] = (pow2[counts] - 1 + mod) % mod。

d. 从 2*i 开始，以 i 为步长，累减 dp[j] mod mod 到 dp[i]。

7.输出 dp[1]，即表示具有最大公约数为 K 的子序列个数。

该算法的时间复杂度为 O(N * log(MAXN))，空间复杂度为 O(MAXN)。

go完整代码如下：

在这里插入图片描述rust完整代码如下：

在这里插入图片描述c++完整代码如下：

在这里插入图片描述c完整代码如下：

在这里插入图片描述