題干：

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 7
?

?

Sample Output

?

1
4

題目大意：

給N個整數(shù)，和一個整數(shù)M。求小于等于M的非負(fù)整數(shù)(1~M)中能被這N個數(shù)中任意一個整除的數(shù)的個數(shù)。

解題報告：

? ?裸的容斥原理啊不解釋了。。。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; ll ans,m,n; ll a[105]; ll LCM(ll a,ll b) {return (a*b)/__gcd(a,b); } void dfs(ll cur,ll lcm,ll id) {if(cur == n) {if(id == 0) return ;if(id&1) ans += ((m)/lcm);else ans-=((m)/lcm);return ;}dfs(cur+1,lcm,id);dfs(cur+1,LCM(a[cur+1],lcm),id+1); } int main() {while(~scanf("%lld%lld",&n,&m)) {for(int i = 1; i<=n; i++) scanf("%lld",a+i);ans=0;dfs(1,a[1],1);//沒選第一個 dfs(1,1,0);//選了第一個 printf("%lld\n",ans);}return 0 ;}

?

總結(jié)

以上是生活随笔為你收集整理的【ZOJ - 2836 】Number Puzzle （容斥原理）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。