AcWing 890. 能被整除的数
原题链接
简单
作者:
AdaMeta
,
2020-02-26 00:36:16
,
所有人可见
,
阅读 665
#define judge
// Author: oceanlvr
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define mp(a, b) make_pair(a, b)
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;
const int ninf = 0xcfcfcfcf;
const double pi = acos(-1.0);
static int faster_iostream = []() {
std::ios::sync_with_stdio(false);
std::cin.tie(NULL);
return 0;
}();
//暴力:每个数被枚举m次总共n个数字 O(mn)
//容斥原理:
/*
S_2:1~n中能被2整除的数字 时间复杂度n/m
S_3:1~n中能被3整除的数字
|S_2+S_3|=|S_2|+|S_3|-|S_2 ^S_3|
时间复杂度 O(2^m) m是集合数
m==16 所以2^6 = 65536
|S_1|求1~n中p的个数,共有 floor(n/p)个
|S_2^S_3|求1~n中p的个数,即既能被2整除又能被3整除的数
即能被6(p2*p3)整除的数,floor(n/(p1+p2))个
....以此类推做到|S1^...^Sn|
算每一个集合时间复杂度是O(m)
因此总的时间复杂度是O(m*2^m)=2^20=1e6
*/
ll res = 0;
int n, m;
int primes[20];
int main() {
#ifndef judge
freopen("E:/yxc/in.txt", "r", stdin);
freopen("E:/yxc/out.txt", "w", stdout);
#endif
cin >> n >> m;
for (int i = 0; i < m; i++) cin >> primes[i];
//总的有2^n-1项 因为对于每一个S要么是1要么是0,并且对于S不能全0
for (int i = 1; i < 1 << m; i++) {
ll t = 1, cnt = 0; // t是当前的元素的个数 cnt当前枚举有几个集合
for (int j = 0; j < m; j++) { //有m个质数
if (i >> j & 1) { //当前的质数被枚举到了,当前质数primes[j]加入
//当前的位数是1时候让cnt++
cnt++;
if ((ll)t * primes[j] >
n) { // n/t=0此时停止 该排列i对更新介绍 该枚举下一个排列了
t = -1;
break;
}
t *= primes[j]; //质数相乘
}
}
if (t != -1) {
if (cnt % 2)//此时是奇数应该加上集合的并
res += n / t;
else//此时偶奇数应该加上集合的并
res -= n / t;
}
}
cout << res << endl;
return 0;
}