网站上的彩票走势图是怎么做的,wordpress 舆情管理,常用的网站建设技术有什么,网络推广运营外包目录 1 基础知识2 模板3 工程化 1 基础知识
题目描述#xff1a;给定整数n和m个不同的质数#xff0c;p1,p2,…pm#xff0c;求1~n中能被这m个质数中至少一个质数整除的数有多少个。其中n和 p i p_i pi在 1 0 9 10^9 109以内#xff0c;而m在16以内。
容斥原理#xf… 目录 1 基础知识2 模板3 工程化 1 基础知识
题目描述给定整数n和m个不同的质数p1,p2,…pm求1~n中能被这m个质数中至少一个质数整除的数有多少个。其中n和 p i p_i pi在 1 0 9 10^9 109以内而m在16以内。
容斥原理 有两个集合 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和 C C C求总和 ∣ A ∪ B ∪ C ∣ |A\cup B\cup C| ∣A∪B∪C∣答案为 ∣ A ∪ B ∪ C ∣ ∣ A ∣ ∣ B ∣ ∣ C ∣ − ∣ A ∩ B ∣ − ∣ A ∩ C ∣ − ∣ B ∩ C ∣ ∣ A ∩ B ∩ C ∣ |A\cup B \cup C||A||B||C|-|A\cap B|-|A\cap C|-|B\cap C||A\cap B \cap C| ∣A∪B∪C∣∣A∣∣B∣∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣∣A∩B∩C∣
进一步抽象 某个类有 n n n中不同的属性记为 P i P_i Pi其中 i 1 , 2 ⋯ n i1,2\cdots n i1,2⋯n拥有属性 P i P_i Pi的对象构成集合 S i S_i Si那么对象总和为 ∣ ∪ i 1 n S i ∣ ∑ i ∣ S i ∣ − ∑ i j ∣ S i ∩ S j ∣ ∑ i j k ∣ S i ∩ S j ∩ S k ∣ − ⋯ ( − 1 ) n − 1 ∣ S 1 ∩ S 2 ⋯ ∩ S n ∣ |\cup_{i1}^{n} S_i|\sum_{i}|S_i|-\sum_{ij}|S_i\cap S_j|\sum_{ijk}|S_i\cap S_j \cap S_k| - \cdots (-1)^{n-1}|S_1\cap S_2 \cdots \cap S_n| ∣∪i1nSi∣i∑∣Si∣−ij∑∣Si∩Sj∣ijk∑∣Si∩Sj∩Sk∣−⋯(−1)n−1∣S1∩S2⋯∩Sn∣ 上式即为容斥原理。
解题思路用容斥原理进行求解且利用二进制表示中的1表示第i个质数选不选以此计算出每一项。 C代码如下
#include iostreamusing namespace std;const int N 20;
int n, m;
int p[N];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;int cnt 0;for (int j 0; j m; j) {if (i j 1) {cnt 1;if ((long long)t * p[j] n) {t -1;break;}t (long long)t * p[j];}}if (t ! -1) {if (cnt % 2 1) {res n / t;} else {res - n / t;}}}cout res endl;return 0;
}2 模板
暂无。。。
3 工程化
暂无。。。
