2023-08-22：請用go語言編寫。給定一個長度為N的正數(shù)數(shù)組，還有一個正數(shù)K， 返回有多
2023-08-22：請用go語言編寫。給定一個長度為N的正數(shù)數(shù)組，還有一個正數(shù)K，
返回有多少子序列的最大公約數(shù)為K。
結(jié)果可能很大，對1000000007取模。
1 <= N <= 10^5，
1 <= arr[i] <= 10^5。
來自騰訊筆試。
來自左程云。
答案2023-08-22：
算法過程分步描述如下：
1.初始化數(shù)組?dp、cnt?和?pow2，長度為 MAXN，全部初始值為 0。
2.讀取數(shù)組長度 N 和正數(shù)數(shù)組 arr。
3.初始化變量 ii 為 0，用于遍歷 arr。
4.設(shè)置 pow2[0] 為 1，表示 2^0。
5.遍歷數(shù)組 arr，從 1 到 N：
a. 讀取當(dāng)前元素 v，即 arr[ii]。
b. 將 v 在 cnt 數(shù)組中的計(jì)數(shù)加 1。
c. 計(jì)算 pow2[i]：pow2[i] = (pow2[i-1] * 2) % mod。
6.從 MAXN-1 循環(huán)到 1：
a. 初始化 counts 為 0，用于統(tǒng)計(jì)具有因子 i 的元素個數(shù)。
b. 遍歷 cnt 數(shù)組，從 i 開始，以 i 為步長，累加 cnt[j] mod mod 到 counts。
c. 計(jì)算 dp[i]：dp[i] = (pow2[counts] - 1 + mod) % mod。
d. 從 2*i 開始，以 i 為步長，累減 dp[j] mod mod 到 dp[i]。
7.輸出 dp[1]，即表示具有最大公約數(shù)為 K 的子序列個數(shù)。
該算法的時間復(fù)雜度為 O(N * log(MAXN))，空間復(fù)雜度為 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++完整代碼如下：
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完整代碼如下：
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;
}
