最美情侣中文字幕电影,在线麻豆精品传媒,在线网站高清黄,久久黄色视频

歡迎光臨散文網(wǎng) 會員登陸 & 注冊

2023-08-22:請用go語言編寫。給定一個長度為N的正數(shù)數(shù)組,還有一個正數(shù)K, 返回有多

2023-08-22 14:08 作者:福大大架構(gòu)師每日一題  | 我要投稿

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++完整代碼如下:

#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;
}

在這里插入圖片描述


2023-08-22:請用go語言編寫。給定一個長度為N的正數(shù)數(shù)組,還有一個正數(shù)K, 返回有多的評論 (共 條)

分享到微博請遵守國家法律
大丰市| 汤原县| 赤城县| 荥经县| 肥城市| 无极县| 嘉善县| 晴隆县| 新丰县| 玛沁县| 津南区| 绥中县| 开鲁县| 宁安市| 乐亭县| 大渡口区| 万荣县| 冕宁县| 枣强县| 竹溪县| 乌拉特前旗| 灯塔市| 拜泉县| 三原县| 如皋市| 武定县| 广丰县| 简阳市| 广南县| 高尔夫| 平顶山市| 濮阳市| 通江县| 德惠市| 沐川县| 五台县| 宁明县| 怀来县| 益阳市| 墨脱县| 延寿县|