如何让搜素引擎不收录自己的网站中国十大it公司

当前位置： 首页 > news >正文

如何让搜素引擎不收录自己的网站,中国十大it公司,下载 app,wordpress布局插件数据结构与算法学习笔记—-容斥原理 author: 明月清了个风 first publish time: 2025.1.30 ps⭐️介绍了容斥原理的相关内容以及一道对应的应用例题。 Acwing 890. 能被整除的数 原题链接 给定一个整数 n n n和 m m m个不同的质数 p 1 …数据结构与算法学习笔记—-容斥原理 author: 明月清了个风 first publish time: 2025.1.30 ps⭐️介绍了容斥原理的相关内容以及一道对应的应用例题。 Acwing 890. 能被整除的数 原题链接 给定一个整数 n n n和 m m m个不同的质数 p 1 , p 2 , ⋯ , p m p_1,p_2,\cdots,p_m p1​,p2​,⋯,pm​。 请你求出 1 ∼ n 1 \sim n 1∼n中能被 p 1 , p 2 , ⋯ , p m p_1,p_2,\cdots,p_m p1​,p2​,⋯,pm​中的至少一个数整除的整数有多少个。 输入格式 第一行包含整数 n n n和 m m m。 第二行包含 m m m个质数。 输出格式 输出一个整数表示满足条件的整数的个数。 数据范围 1 ≤ m ≤ 16 1 \le m \le 16 1≤m≤16, 1 ≤ n , p i ≤ 1 0 9 1 \le n, p_i \le 10^9 1≤n,pi​≤109 思路 容斥原理是一种重要的组合数学方法用于解决多个集合的元素计数问题。它的核心思想是通过对集合进行交集与并集的操作减去重复计算的部分从而准确地计算出多个集合的并集中元素的总数。 两个集合的容斥原理 设 A A A和 B B B是两个集合则它们的并集 A ∪ B A \cup B A∪B的元素个数为 ∣ A ∪ B ∣ ∣ A ∣ ∣ B ∣ − ∣ A ∩ B ∣ |A \cup B| |A| |B| - |A \cap B| ∣A∪B∣∣A∣∣B∣−∣A∩B∣ 其中 ∣ A ∣ |A| ∣A∣和 ∣ B ∣ |B| ∣B∣分别是集合 A A A和 B B B的元素个数 ∣ A ∩ B ∣ |A \cap B| ∣A∩B∣是集合 A A A和 B B B的交集的元素个数。 三个集合的容斥原理 设 A A A、 B B B和 C C C是三个集合则它们的并集 A ∪ B ∪ C A \cup B \cup C A∪B∪C的元素个数为 ∣ 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| ∣A∪B∪C∣∣A∣∣B∣∣C∣−∣A∩B∣−∣B∩C∣−∣C∩A∣∣A∩B∩C∣ 其中 ∣ A ∣ |A| ∣A∣、 ∣ B ∣ |B| ∣B∣和 ∣ C ∣ |C| ∣C∣分别是集合 A A A、 B B B和 C C C的元素个数 ∣ A ∩ B ∣ |A \cap B| ∣A∩B∣、 ∣ B ∩ C ∣ |B \cap C| ∣B∩C∣和 ∣ C ∩ A ∣ |C \cap A| ∣C∩A∣分别是集合 A A A和 B B B、 B B B和 C C C、 C C C和 A A A的交集的元素个数 ∣ A ∩ B ∩ C ∣ |A \cap B \cap C| ∣A∩B∩C∣是集合 A A A、 B B B和 C C C的交集的元素个数。 n n n个集合的容斥原理 设 A 1 , A 2 , … , A n A_1, A_2, \ldots, A_n A1​,A2​,…,An​是 n n n个集合则它们的并集 A 1 ∪ A 2 ∪ … ∪ A n A_1 \cup A_2 \cup \ldots \cup A_n A1​∪A2​∪…∪An​的元素个数为 ∣ 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 An| \sum{i1}^{n} |Ai| - \sum{1 \leq i j \leq n} |A_i \cap Aj| \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 An| ∣A1​∪A2​∪…∪An​∣∑i1n​∣Ai​∣−∑1≤ij≤n​∣Ai​∩Aj​∣∑1≤ijk≤n​∣Ai​∩Aj​∩Ak​∣−⋯(−1)n−1∣A1​∩A2​∩…∩An​∣ 其中求和符号表示对所有可能的集合组合进行求和 ( − 1 ) n − 1 (-1)^{n-1} (−1)n−1表示当集合的交集数量即下标集合的大小为奇数时取正号为偶数时取负号。 对于 n n n个集合的容斥原理公式来说最后共有 2 n 2^n 2n项因为每一项都可以看做是一个组合数比如 ∑ i 1 n ∣ A i ∣ \sum{i1}^{n}|Ai| ∑i1n​∣Ai​∣中共有是 n n n项因为相当于 C n 1 C{n}^{1} Cn1​种方案数对于 ∑ 1 ≤ i j ≤ n ∣ A i ∩ A j ∣ \sum_{1 \leq i j \leq n} |A_i \cap Aj| ∑1≤ij≤n​∣Ai​∩Aj​∣也同样是这样相当于 C n 2 C{n}^{2} Cn2​种方案数那么所有的项目就相当于 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项但是其实所有集合都不选也是一项也就是 C n 0 Cn^0 Cn0​只是没有显式的计算他因此最开始说共有 2 n 2^n 2n项。 y总还讲了另外一个等式这个式子表明了容斥原理的核心思想每个元素只被统计一次。 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)^{k1}C_{k}^{k} 1 Ck1​−Ck2​Ck3​−…(−1)k1Ckk​1 这个等式表明在容斥原理的交替求和公式中每个元素在所有可能的集合组合交集中出现的次数经过正负交替相加后总和等于1从而确保了每个元素在最终的计算中只被统计了一次。 这里再回到题目来看我们需要统计 1 ∼ n 1 \sim n 1∼n中至少被一个所给的数整除的数有多少个也就是说如果一个数能被好几个数整除也只统计一次如果我们用暴力做法需要对 n n n个数都遍历 m m m个数对比时间复杂度为 O ( n ⋅ m ) O(n \cdot m) O(n⋅m)会超时但是我们使用容斥原理进行统计的话就能将时间复杂度降低到 O ( 2 m ) O(2^m) O(2m)。 首先对于每一个给出的质数p_i都会有一个集合表示所有能被他整除的数要关注的是这个集合中元素的个数而不是这些数是哪些数。这个数量我们可以通过 ⌊ n p i ⌋ \lfloor \frac{n}{p_i} \rfloor ⌊pi​n​⌋计算得出同样的对于同时是多个质数的倍数的集合中元素的个数也可以这样计算得到例如 ⌊ n p i p j ⌋ \lfloor \frac{n}{p_i p_j} \rfloor ⌊pi​pj​n​⌋的形式我们可以通过这样的方式处理出所有集合包含元素的个数。 然后通过对上面n个元素对应的容斥原理计算公式进行观察可以发现当一个元素被包含在偶数个集合中时那就应该减去集合数为奇数时加上同样用上面的来举例所有的只被一个质数整除的元素集合的数目 ⌊ n p i ⌋ \lfloor \frac{n}{p_i} \rfloor ⌊pi​n​⌋都应该被加到答案 r e s res res中区所有被两个质数整除的元素集合的数目 ⌊ n p i p j ⌋ \lfloor \frac{n}{p_i p_j} \rfloor ⌊pi​pj​n​⌋都应该从答案中减去。 至此题目的思路已经理清了需要考虑的是代码的逻辑我们要统计的有两个东西 所有集合的大小。每个集合是能被几个质数整除。 这里就用到了上面对于容斥原理公式包含项数的结果了一共 2 m − 1 2^m - 1 2m−1项一共有 m m m个质数那么我们可以通过统计 1 ∼ 2 m 1 \sim 2^m 1∼2m一共 2 m − 1 2^m - 1 2m−1个数代表所有的集合每个数的二进制表示中的 1 1 1的数量表示这个集合是被几个质数整除的同时集合的大小可以在这个过程中同时处理出来将所有质数存在数组p[N]中记录一个数t 1当第i位为1时就将t * p[i]遍历完这个数的二进制的所有位后通过num n / t得到该集合的大小具体的看代码吧 代码 #include iostream #include cstring #include cstdio #include algorithmusing 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; }