中文亚洲精品无码_熟女乱子伦免费_人人超碰人人爱国产_亚洲熟妇女综合网

當(dāng)前位置: 首頁(yè) > news >正文

做網(wǎng)站小編怎么樣做網(wǎng)絡(luò)推廣可以通過(guò)哪些渠道推廣

做網(wǎng)站小編怎么樣,做網(wǎng)絡(luò)推廣可以通過(guò)哪些渠道推廣,馬鞍山網(wǎng)站開(kāi)發(fā),校園平臺(tái)網(wǎng)站建設(shè)感悟數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)筆記----容斥原理 author: 明月清了個(gè)風(fēng) first publish time: 2025.1.30 ps??介紹了容斥原理的相關(guān)內(nèi)容以及一道對(duì)應(yīng)的應(yīng)用例題。 Acwing 890. 能被整除的數(shù) [原題鏈接](890. 能被整除的數(shù) - AcWing題庫(kù)) 給定一個(gè)整數(shù) n n n和 m m m個(gè)不同的質(zhì)數(shù) p 1 …

數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)筆記----容斥原理

@@ author: 明月清了個(gè)風(fēng)
@@ first publish time: 2025.1.30

ps??介紹了容斥原理的相關(guān)內(nèi)容以及一道對(duì)應(yīng)的應(yīng)用例題。


Acwing 890. 能被整除的數(shù)

[原題鏈接](890. 能被整除的數(shù) - AcWing題庫(kù))

給定一個(gè)整數(shù) n n n m m m個(gè)不同的質(zhì)數(shù) p 1 , p 2 , ? , p m p_1,p_2,\cdots,p_m p1?,p2?,?,pm?。

請(qǐng)你求出 1 ~ n 1 \sim n 1n中能被 p 1 , p 2 , ? , p m p_1,p_2,\cdots,p_m p1?,p2?,?,pm?中的至少一個(gè)數(shù)整除的整數(shù)有多少個(gè)。

輸入格式

第一行包含整數(shù) n n n m m m。

第二行包含 m m m個(gè)質(zhì)數(shù)。

輸出格式

輸出一個(gè)整數(shù),表示滿(mǎn)足條件的整數(shù)的個(gè)數(shù)。

數(shù)據(jù)范圍

1 ≤ m ≤ 16 1 \le m \le 16 1m16,

1 ≤ n , p i ≤ 1 0 9 1 \le n, p_i \le 10^9 1n,pi?109

思路

容斥原理是一種重要的組合數(shù)學(xué)方法,用于解決多個(gè)集合的元素計(jì)數(shù)問(wèn)題。它的核心思想是通過(guò)對(duì)集合進(jìn)行交集與并集的操作,減去重復(fù)計(jì)算的部分,從而準(zhǔn)確地計(jì)算出多個(gè)集合的并集中元素的總數(shù)。

  1. 兩個(gè)集合的容斥原理

設(shè) A A A B B B是兩個(gè)集合,則它們的并集 A ∪ B A \cup B AB的元素個(gè)數(shù)為:

∣ A ∪ B ∣ = ∣ A ∣ + ∣ B ∣ ? ∣ A ∩ B ∣ |A \cup B| = |A| + |B| - |A \cap B| AB=A+B?AB

其中, ∣ A ∣ |A| A ∣ B ∣ |B| B分別是集合 A A A B B B的元素個(gè)數(shù), ∣ A ∩ B ∣ |A \cap B| AB是集合 A A A B B B的交集的元素個(gè)數(shù)。

  1. 三個(gè)集合的容斥原理

設(shè) A A A、 B B B C C C是三個(gè)集合,則它們的并集 A ∪ B ∪ C A \cup B \cup C ABC的元素個(gè)數(shù)為:

∣ A ∪ B ∪ C ∣ = ∣ A ∣ + ∣ B ∣ + ∣ C ∣ ? ∣ A ∩ B ∣ ? ∣ B ∩ C ∣ ? ∣ C ∩ A ∣ + ∣ A ∩ B ∩ C ∣ |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |C \cap A| + |A \cap B \cap C| ABC=A+B+C?AB?BC?CA+ABC

其中, ∣ A ∣ |A| A、 ∣ B ∣ |B| B ∣ C ∣ |C| C分別是集合 A A A、 B B B C C C的元素個(gè)數(shù), ∣ A ∩ B ∣ |A \cap B| AB ∣ B ∩ C ∣ |B \cap C| BC ∣ C ∩ A ∣ |C \cap A| CA分別是集合 A A A B B B、 B B B C C C、 C C C A A A的交集的元素個(gè)數(shù), ∣ A ∩ B ∩ C ∣ |A \cap B \cap C| ABC是集合 A A A、 B B B C C C的交集的元素個(gè)數(shù)。

  1. n n n個(gè)集合的容斥原理

設(shè) A 1 , A 2 , … , A n A_1, A_2, \ldots, A_n A1?,A2?,,An? n n n個(gè)集合,則它們的并集 A 1 ∪ A 2 ∪ … ∪ A n A_1 \cup A_2 \cup \ldots \cup A_n A1?A2?An?的元素個(gè)數(shù)為:

∣ A 1 ∪ A 2 ∪ … ∪ A n ∣ = ∑ i = 1 n ∣ A i ∣ ? ∑ 1 ≤ i < j ≤ n ∣ A i ∩ A j ∣ + ∑ 1 ≤ i < j < k ≤ n ∣ A i ∩ A j ∩ A k ∣ ? ? + ( ? 1 ) n ? 1 ∣ A 1 ∩ A 2 ∩ … ∩ A n ∣ |A_1 \cup A_2 \cup \ldots \cup A_n| = \sum_{i=1}^{n} |A_i| - \sum_{1 \leq i < j \leq n} |A_i \cap A_j| + \sum_{1 \leq i < j < k \leq n} |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n-1} |A_1 \cap A_2 \cap \ldots \cap A_n| A1?A2?An?=i=1n?Ai??1i<jn?Ai?Aj?+1i<j<kn?Ai?Aj?Ak???+(?1)n?1A1?A2?An?

其中,求和符號(hào)表示對(duì)所有可能的集合組合進(jìn)行求和, ( ? 1 ) n ? 1 (-1)^{n-1} (?1)n?1表示當(dāng)集合的交集數(shù)量(即下標(biāo)集合的大小)為奇數(shù)時(shí)取正號(hào),為偶數(shù)時(shí)取負(fù)號(hào)。

對(duì)于 n n n個(gè)集合的容斥原理公式來(lái)說(shuō),最后共有 2 n 2^n 2n項(xiàng),因?yàn)槊恳豁?xiàng)都可以看做是一個(gè)組合數(shù),比如 ∑ i = 1 n ∣ A i ∣ \sum_{i=1}^{n}|A_i| i=1n?Ai?中共有是 n n n項(xiàng),因?yàn)橄喈?dāng)于 C n 1 C_{n}^{1} Cn1?種方案數(shù);對(duì)于 ∑ 1 ≤ i < j ≤ n ∣ A i ∩ A j ∣ \sum_{1 \leq i < j \leq n} |A_i \cap A_j| 1i<jn?Ai?Aj?也同樣是這樣,相當(dāng)于 C n 2 C_{n}^{2} Cn2?種方案數(shù);那么所有的項(xiàng)目就相當(dāng)于 C n 1 + C n 2 + C n 3 + ? + C n n = 2 n ? 1 C_n^{1} + C_n^{2} + C_n^{3} + \cdots + C_n^{n} = 2^n - 1 Cn1?+Cn2?+Cn3?+?+Cnn?=2n?1項(xiàng),但是其實(shí)所有集合都不選也是一項(xiàng),也就是 C n 0 C_n^0 Cn0?,只是沒(méi)有顯式的計(jì)算他,因此最開(kāi)始說(shuō)共有 2 n 2^n 2n項(xiàng)。

y總還講了另外一個(gè)等式,這個(gè)式子表明了容斥原理的核心思想:每個(gè)元素只被統(tǒng)計(jì)一次
C k 1 ? C k 2 + C k 3 ? … + ( ? 1 ) k + 1 C k k = 1 C_{k}^{1} - C_{k}^{2} + C_{k}^{3} - \ldots + (-1)^{k+1}C_{k}^{k} = 1 Ck1??Ck2?+Ck3??+(?1)k+1Ckk?=1
這個(gè)等式表明,在容斥原理的交替求和公式中,每個(gè)元素在所有可能的集合組合(交集)中出現(xiàn)的次數(shù),經(jīng)過(guò)正負(fù)交替相加后,總和等于1,從而確保了每個(gè)元素在最終的計(jì)算中只被統(tǒng)計(jì)了一次。

這里再回到題目來(lái)看,我們需要統(tǒng)計(jì) 1 ~ n 1 \sim n 1n中至少被一個(gè)所給的數(shù)整除的數(shù)有多少個(gè),也就是說(shuō)如果一個(gè)數(shù)能被好幾個(gè)數(shù)整除,也只統(tǒng)計(jì)一次,如果我們用暴力做法,需要對(duì) n n n個(gè)數(shù)都遍歷 m m m個(gè)數(shù)對(duì)比,時(shí)間復(fù)雜度為 O ( n ? m ) O(n \cdot m) O(n?m)會(huì)超時(shí),但是我們使用容斥原理進(jìn)行統(tǒng)計(jì)的話,就能將時(shí)間復(fù)雜度降低到 O ( 2 m ) O(2^m) O(2m)。

首先,對(duì)于每一個(gè)給出的質(zhì)數(shù)p_i,都會(huì)有一個(gè)集合表示所有能被他整除的數(shù),要關(guān)注的是這個(gè)集合中元素的個(gè)數(shù),而不是這些數(shù)是哪些數(shù)。這個(gè)數(shù)量我們可以通過(guò) ? n p i ? \lfloor \frac{n}{p_i} \rfloor ?pi?n??計(jì)算得出,同樣的對(duì)于同時(shí)是多個(gè)質(zhì)數(shù)的倍數(shù)的集合中元素的個(gè)數(shù)也可以這樣計(jì)算得到,例如 ? n p i p j ? \lfloor \frac{n}{p_i p_j} \rfloor ?pi?pj?n??的形式,我們可以通過(guò)這樣的方式處理出所有集合包含元素的個(gè)數(shù)。

然后,通過(guò)對(duì)上面n個(gè)元素對(duì)應(yīng)的容斥原理計(jì)算公式進(jìn)行觀察可以發(fā)現(xiàn),當(dāng)一個(gè)元素被包含在偶數(shù)個(gè)集合中時(shí),那就應(yīng)該減去,集合數(shù)為奇數(shù)時(shí)加上,同樣用上面的來(lái)舉例,所有的只被一個(gè)質(zhì)數(shù)整除的元素集合的數(shù)目 ? n p i ? \lfloor \frac{n}{p_i} \rfloor ?pi?n??都應(yīng)該被加到答案 r e s res res中區(qū),所有被兩個(gè)質(zhì)數(shù)整除的元素集合的數(shù)目 ? n p i p j ? \lfloor \frac{n}{p_i p_j} \rfloor ?pi?pj?n??都應(yīng)該從答案中減去。

至此,題目的思路已經(jīng)理清了,需要考慮的是代碼的邏輯,我們要統(tǒng)計(jì)的有兩個(gè)東西

  1. 所有集合的大小。
  2. 每個(gè)集合是能被幾個(gè)質(zhì)數(shù)整除。

這里就用到了上面對(duì)于容斥原理公式包含項(xiàng)數(shù)的結(jié)果了,一共 2 m ? 1 2^m - 1 2m?1項(xiàng),一共有 m m m個(gè)質(zhì)數(shù),那么我們可以通過(guò)統(tǒng)計(jì) 1 ~ 2 m 1 \sim 2^m 12m,一共 2 m ? 1 2^m - 1 2m?1個(gè)數(shù)代表所有的集合,每個(gè)數(shù)的二進(jìn)制表示中的 1 1 1的數(shù)量表示這個(gè)集合是被幾個(gè)質(zhì)數(shù)整除的,同時(shí),集合的大小可以在這個(gè)過(guò)程中同時(shí)處理出來(lái),將所有質(zhì)數(shù)存在數(shù)組p[N]中,記錄一個(gè)數(shù)t = 1,當(dāng)?shù)?code>i位為1時(shí),就將t *= p[i],遍歷完這個(gè)數(shù)的二進(jìn)制的所有位后,通過(guò)num = n / t得到該集合的大小,具體的看代碼吧

代碼

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>using namespace std;typedef long long LL;const int N = 20;int p[N];
int n, m;int main()
{cin >> n >> m;for(int i = 0; i < m; i ++) cin >> p[i];int res = 0;for(int i = 1; i < 1 << m; i ++){int t = 1, cnt = 0;for(int j = 0; j < m; j ++){if(i >> j & 1){if((LL)t * p[j] > n){t = -1;break;}t *= p[j];cnt ++;}}if(t == -1) continue;if(cnt % 2) res += n / t;else res -= n / t;}cout << res << endl;return 0;
}
http://www.risenshineclean.com/news/49889.html

相關(guān)文章:

  • 網(wǎng)站建設(shè)優(yōu)化公司cps推廣接單平臺(tái)
  • 網(wǎng)站開(kāi)發(fā)服務(wù)商百度網(wǎng)頁(yè)版網(wǎng)址
  • 能查個(gè)人信息的網(wǎng)站百度競(jìng)價(jià)托管代運(yùn)營(yíng)公司
  • 營(yíng)銷(xiāo)型網(wǎng)站建設(shè)定制網(wǎng)絡(luò)營(yíng)銷(xiāo)的四種模式
  • 怎樣免費(fèi)建立自己網(wǎng)站長(zhǎng)春做網(wǎng)站推薦選吉網(wǎng)傳媒好
  • 什么是網(wǎng)站app惠州seo管理
  • wordpress手機(jī)圖片站蘇州百度代理公司
  • 平面設(shè)計(jì)網(wǎng)站大全有哪些成人計(jì)算機(jī)培訓(xùn)機(jī)構(gòu)哪個(gè)最好
  • 一些好用的網(wǎng)站個(gè)人博客網(wǎng)站設(shè)計(jì)畢業(yè)論文
  • 做自媒體的網(wǎng)站谷歌推廣開(kāi)戶(hù)多少費(fèi)用
  • 自己做的網(wǎng)站如何加視頻長(zhǎng)春seo排名公司
  • wordpress做的好的網(wǎng)站友情鏈接的形式有哪些
  • 深圳網(wǎng)站建設(shè)公司 交通如何推廣app更高效
  • 珠海網(wǎng)站優(yōu)化百度導(dǎo)航2023年最新版
  • 怎樣查看wordpress用的什么主題網(wǎng)站seo工具
  • 安徽六安郵政編碼seo快速排名軟件app
  • 關(guān)鍵詞的分類(lèi)和優(yōu)化seo關(guān)鍵詞首頁(yè)排名代發(fā)
  • 企業(yè)宣傳片文案大全北京網(wǎng)站優(yōu)化排名
  • 得物app公司域名seo查詢(xún)
  • 做網(wǎng)站baidunongmin南寧seo優(yōu)化公司
  • 做網(wǎng)站怎么插音樂(lè)循環(huán)西安網(wǎng)站制作價(jià)格
  • 互聯(lián)網(wǎng)站備案登記表石家莊網(wǎng)站建設(shè)排名
  • 專(zhuān)業(yè)杭州網(wǎng)站建設(shè)今日頭條新聞最新事件
  • 網(wǎng)站的排版好看點(diǎn)擊進(jìn)入官方網(wǎng)站
  • 濰坊網(wǎng)站定制 優(yōu)幫云谷歌搜索引擎入口2023
  • 浙江昆侖建設(shè)集團(tuán)網(wǎng)站seo技術(shù)培訓(xùn)沈陽(yáng)
  • 域名年費(fèi)價(jià)格表新野seo公司
  • 代碼大全可復(fù)制武漢seo價(jià)格
  • 江蘇藝居建設(shè)有限公司網(wǎng)站如何做市場(chǎng)營(yíng)銷(xiāo)推廣
  • 商城網(wǎng)站建設(shè)適合于哪類(lèi)企業(yè)營(yíng)業(yè)推廣促銷(xiāo)