本文共 1232 字，大约阅读时间需要 4 分钟。
Given a list of integers (A1, A2, …, An), and a positive integer M, please find the number of positive integers that are not greater than M and dividable by any integer from the given list.
Input
The input contains several test cases.For each test case, there are two lines. The first line contains N (1 <= N <= 10) and M (1 <= M <= 200000000), and the second line contains A1, A2, …, An(1 <= Ai <= 10, for i = 1, 2, …, N).
Output
For each test case in the input, output the result in a single line.Sample Input
3 2 2 3 7 3 6 2 3 7Sample Output
1 4 抽空起来整理训练的题目,还是容斥原理.这次看就比原来明白多了… 怎么说呢,感觉容斥原理本质上就是加奇减偶.然后我们根据题意去在这个基础上做一些改变.这个题目的本意是,给你n个数,再给你一个m,找出不大于m,而且至少能被这n个数中一个数整除的数的个数.典型的容斥定理,a+b+c-ab-ac-bc+abc…就是这样奇加偶减.dfs做就可以了.集体解释看代码. 代码如下:#include#include #include #include #include #define ll long longusing namespace std;const int maxx=11;ll n,m,ans;ll vis[maxx];ll b[maxx];int cnt;ll gcd(ll x,ll y)//求gcd,最大公因数{ if(x%y==0) return y; else return gcd(y,x%y);}ll lcm(ll x,ll y)//最小公倍数{ return x/gcd(x,y)*y;}void dfs(ll cur,ll ant,ll num)//ant代表数组下标,防止重复搜索..num代表几个数字..来进行奇加偶减{ if(cur>m||num>cnt) return ; for(int i=ant;i
容斥原理要多思考.推出公式来就好了…
努力加油a啊,(o)/~.转载地址：http://pzxvi.baihongyu.com/