2023-08-22：请用go语言编写。给定一个长度为N的正数数组，还有一个正数K，
返回有多少子序列的最大公约数为K。
结果可能很大，对1000000007取模。
1 <= N <= 10^5，
1 <= arr[i] <= 10^5。
来自腾讯笔试。
来自左程云。
答案2023-08-22：
算法过程分步描述如下：
1.初始化数组 dp、cnt 和 pow2，长度为 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完整代码如下：
package main
import (
"fmt"
)
const MAXN = 100001
const mod = 1000000007
var dp = make([]int64, MAXN)
var cnt = make([]int64, MAXN)
var pow2 = make([]int64, MAXN)
func main() {
buf := []int{7, 1, 3, 5, 15, 3, 105, 35}
ii := 0
n := buf[ii]
ii++
pow2[0] = 1
for i := 1; i <= n; i++ {
v := buf[ii]
ii++
cnt[v]++
pow2[i] = (pow2[i-1] * 2) % mod
}
for i := MAXN - 1; i >= 1; i-- {
counts := int64(0)
for j := i; j < MAXN; j += i {
counts = (counts + cnt[j]) % mod
}
dp[i] = (pow2[counts] - 1 + mod) % mod
for j := 2 * i; j < MAXN; j += i {
dp[i] = (dp[i] - dp[j] + mod) % mod
}
}
fmt.Println(dp[1])
}
rust完整代码如下：
const MAXN: usize = 100001;
const MOD: i64 = 1000000007;
fn main() {
let buf = [7, 1, 3, 5, 15, 3, 105, 35];
let mut i: usize = 0;
let n = buf[i];
i += 1;
let mut dp = vec![0; MAXN];
let mut cnt = vec![0; MAXN];
let mut pow2 = vec![0; MAXN];
pow2[0] = 1;
for j in 1..=n {
let v = buf[i];
i += 1;
cnt[v] += 1;
pow2[j] = (pow2[j - 1] * 2) % MOD;
}
for i in (1..MAXN).rev() {
let mut counts = 0;
for j in (i..MAXN).step_by(i) {
counts = (counts + cnt[j]) % MOD;
}
dp[i] = (pow2[counts as usize] - 1 + MOD) % MOD;
for j in ((2 * i)..MAXN).step_by(i) {
dp[i] = (dp[i] - dp[j] + MOD) % MOD;
}
}
println!("{}", dp[1]);
}
c++完整代码如下：
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 100001;
const int mod = 1000000007;
vector<long long> dp(MAXN);
vector<long long> cnt(MAXN);
vector<long long> pow2(MAXN);
int main() {
int buf[] = { 7, 1, 3, 5, 15, 3, 105, 35 };
int ii = 0;
int n = buf[ii++];
pow2[0] = 1;
for (int i = 1; i <= n; i++) {
int v = buf[ii++];
cnt[v]++;
pow2[i] = (pow2[i - 1] * 2) % mod;
}
for (int i = MAXN - 1; i >= 1; i--) {
long long counts = 0;
for (int j = i; j < MAXN; j += i) {
counts = (counts + cnt[j]) % mod;
}
dp[i] = (pow2[counts] - 1 + mod) % mod;
for (int j = 2 * i; j < MAXN; j += i) {
dp[i] = (dp[i] - dp[j] + mod) % mod;
}
}
cout << dp[1] << endl;
return 0;
}
c完整代码如下：
#include <stdio.h>
#define MAXN 100001
#define mod 1000000007
long long dp[MAXN];
long long cnt[MAXN];
long long pow2[MAXN];
int main() {
int n;
int buf[] = { 7, 1, 3, 5, 15, 3, 105, 35 };
int ii = 0;
n = buf[ii++];
pow2[0] = 1;
for (int i = 1; i <= n; i++) {
int v = buf[ii++];
cnt[v]++;
pow2[i] = (pow2[i - 1] * 2) % mod;
}
for (int i = MAXN - 1; i >= 1; i--) {
long long counts = 0;
for (int j = i; j < MAXN; j += i) {
counts = (counts + cnt[j]) % mod;
}
dp[i] = (pow2[counts] - 1 + mod) % mod;
for (int j = 2 * i; j < MAXN; j += i) {
dp[i] = (dp[i] - dp[j] + mod) % mod;
}
}
printf("%lld\n", dp[1]);
return 0;
}