东莞网站优化费用_个人能做网站吗_跨境电商平台排行榜前十名_淘宝搜索关键词排名

题目

解题思路

什么是容斥原理：

具体到题目中：
S₁代表1到n中能被质数p₁整除的数的集合，而|S₁|代表1~n中能被质数p₁整除的数的数量;

则题目所求结果:
res = | S₁ U S₂ U S₃ … U S_m | = |S₁| + |S₂| + |S₃| + … + |S_m| (C(m, 1)个数) - (|S₁ ∩ S₂| + |S₁ ∩ S₃| + …) (C(m, 2)个数) + … + (-1)^n-1(S₁∩S₂∩S₃…∩S_m) (C(m, m) 个数)

同时C(m, 0) + C(m ,1) + C(m, 2) + C(m , 3) + … C(m, m) = 2^m(相当于一个球袋中拿走任意数量的球的方案量， 即每个球都只有拿走与不拿走两个选项，总方案量就是2^m)

所以，总循环次数就是2^m - 1,即可得到答案res；

具体实现方法：

代码实现

#include <iostream>
#include <algorithm>using namespace std;typedef long long LL;const int N = 20;int p[N];int main()
{int n, m;cin >> n >> m;// 用p数组存储m个质数for (int i = 0; i < m; i ++ ) cin >> p[i];int res = 0;// 每一个i代表一种可能的取法，最外层的循环遍历置2的m次方后，可以取完所有的取法// 从1开始枚举，枚举到1 << m（左移m位。左移一位相当于乘2，右移一位相当于除2），即2的m次方；for (int i = 1; i < 1 << m ; i ++ )//等同于i < 2^m^{// t代表当前所有质数的乘积，s代表什么当前选法包含几个集合int t = 1, s = 0;// 枚举m个质数，依次计算容斥原理的公式for (int j = 0; j < m; j ++ ){// i右移j位与上1，即如果当前位是1的话//>>的优先级大于&，所以是先>>再&!if (i >> j & 1){if ((LL)t * p[j] > n)//主要原因是为了防止爆long long,导致出现错误答案！！！{t = -1;break; // break的作用域是跳出整个循环}// 将该质数乘到t中t *= p[j];// s表示当前选法中有多少个集合s ++ ;}}// 带入公式求解一个S// 如果t不等于-1（-1是给定的flag值）if (t != -1){//根据公式，如果s是偶数要减去，是奇数要加上if (s % 2) res += n / t;else res -= n / t;}}cout << res << endl;return 0;
}

具体代码块分析

假设m = 4的情况下：

 // 每一个i代表一种可能的取法，最外层的循环遍历置2的m次方后，可以取完所有的取法for (int i = 1; i < 1 << m ; i ++ )//等同于i < 2^m^

这段代码等同于：i = 0001; i < 10000; i ++ (二进制);
而不同的i代表选择了不同的集合：
比如i = 0101时， 选择了S₁和S₃这两个集合。
继续带入下面的代码：

        for (int j = 0; j < m; j ++ ){// i右移j位与上1，即如果当前位是1的话//>>的优先级大于&，所以是先>>再&!if (i >> j & 1){if ((LL)t * p[j] > n)//主要原因是为了防止爆long long 的数据范围,导致出现错误！！！{t = -1;break;}// 将该质数乘到t中t *= p[j];// s表示当前选法中有多少个集合s ++ ;}}// 带入公式求解一个S// 如果t不等于-1（-1是给定的flag值）if (t != -1){//根据公式，如果s是偶数要减去，是奇数要加上if (s % 2) res += n / t;else res -= n / t;}

实际上计算的是|S₁∩S₃|的值；