题目描述

给定一个整数$n$和$m$个不同的质数$p1,p2,…,pm$。

请你求出$1~n$中能被$p1,p2,…,pm$中的至少一个数整除的整数有多少个。
数据范围
$1≤m≤16, 1≤n, pi≤10^9 $

样例

输入样例：
10 2
2 3

输出样例：
7

做法：

至少一个数整除的整数可以用容斥原理求得

相关链接： 数学知识笔记
如何枚举集合两两间的并集呢？
可以使用dfs算法，暴力枚举每一个可能的排列。
又由于$C_n^0+C_n^1+C_n^2+…+C_n^n=2^n$所以，要运行$2^n-C_n^0$次，也就是$2^n-1$次

C++ 代码

#include<bits/stdc++.h>
using namespace std;
#define re register
#define Re register
#define ll long long
#define MAXN 30
int n,m;
ll ans,p[MAXN];
void dfs(int step,ll cnt,int opt){//step代表当前状态在数组中的位置，CNT代表目前的总乘积，opt代表目前是+还是-
    if(cnt > n)return;//剪枝，忽略cnt大于0的情况
    if(step)ans += n / cnt * opt;
    opt = -opt;
    for(Re int i = step + 1;i <= m;i++){
        dfs(i,cnt * p[i],opt);
    }
    return;
}
int main() {
    cin >> n >> m;
    for(Re int i = 1;i <= m;i++){
        cin >> p[i];
    }
    dfs(0,1,-1);
    cout << ans << endl;
    return 0;
}