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 = 100001const 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;}
复制代码
评论