石家庄做网站建设搜索引擎优化要考虑哪些方面

思路：

（1）需求：求对于1~n中至少能被p1~pm至少1个整除的数的个数，由于都是质数，彼此互质，不需要进行质因子分解，根据容斥原理，

                        res = n/p1 + n/p2 +... + n/pm - n /(p1p2) - n/(p1p3) - ...；

显然只需要讨论p1~pm所有组合形式t，如果小于等于n:

1. 如果是奇数个质数组成，则加等于n/t,否则减等于n/t；

最终结果即为1~n之间的所有至少能被p1~pm之间1个数整除的数的个数。

（2）注意用二进制讨论组合方式时，不能全零，全零即为1，不满足至少被其中一个整除。

代码：

#include<bits/stdc++.h>using namespace std;
const int N = 20,M = 1 << N;
typedef long long LL;LL p[N];int main()
{int n,m;cin >> n >> m;for(int i = 0;i < m;i ++)cin >> p[i];LL res = 0;for(int i = 1;i < (1 << m);i ++){LL t = 1,cnt = 0;for(int j = 0;j < m;j ++){if(i>>j &1 == 1){cnt ++;t *= p[j];if(t > n) break;}}if(t <= n){if(cnt %2 == 0) res -= n/t;else res += n/t;}}cout << res << endl;return 0;
}