本文共 1182 字，大约阅读时间需要 3 分钟。

题目描述：

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

请你求出1~n中能被p1,p2,…,pm中的至少一个数整除的整数有多少个。

输入格式

第一行包含整数n和m。第二行包含m个质数。

输出格式

输出一个整数，表示满足条件的整数的个数。

数据范围

1≤m≤16,

输入样例：

10 22 3

输出样例：

7

分析：

本题考察容斥原理。即。通俗的说，就是求n个集合的并集，需要先将n个集合加起来，然后减去所有两个集合的交集，在加上所有三个集合的交集，...。这样交替加减下去就得到了n个集合的并集了。题目要求1-n中能被至少给定质数中一个整除数的个数。比如n = 10，给定p = 2,3.能被2整除的数有2,4,6,8,10；能被3整除的数有3 6 9；能被2,3同时整除的数有6，故一共有5 + 3 - 1 = 7个数。而1到n中能被p整除数的个数为n / p，问题仅在于给定m个质数，如何从中选出需要的若干个数。

从m个质数中选数使用了在状态压缩中常用的位运算操作，1到2^m - 1对应了所有数的选择情况，对应位为1表示选中了，对应位为0表示未选中。比如m = 5，数21 = 10101表示选中了第1,3,5个质数。用此方式确定选中的质数及其乘积，当被选中的质数个数是奇数时，我们就加上1到n中能被这些数乘积整除的数的个数；是偶数时就减去能被这些数整除数的个数。

#include 
   
    using namespace std;typedef long long ll;int p[20];int main(){    int n,m;    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,s = 0;        for(int j = 0;j < m;j++){            if(i >> j & 1){                if((ll)t * p[j] > n){                    t = -1;                    break;                }                t *= p[j];                s++;            }        }        if(t != -1){            if(s % 2)   res += n / t;            else    res -= n / t;        }    }    cout<
    
     <
    
   

转载地址：https://blog.csdn.net/qq_30277239/article/details/103822542 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！