首页 > 代码库 > [容斥原理] zoj 2836 Number Puzzle
[容斥原理] zoj 2836 Number Puzzle
题目链接:
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1836
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
Author: MAO, Yiqiang
Source: Zhejiang University Local Contest 2007
题目意思:
给n个数,求不超过m的能被这n个数中任意一个整除的数的个数。
解题思路:
简单容斥原理
先求出能被一个数整除的数的个数,再减去能被两个数整除的,再加上能被三个数整除的.....
可以用dfs模拟求。
注意能被多个数整除的,要求出他们的最小公倍数。
代码:
//#include<CSpreadSheet.h> #include<iostream> #include<cmath> #include<cstdio> #include<sstream> #include<cstdlib> #include<string> #include<string.h> #include<cstring> #include<algorithm> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<queue> #include<ctime> #include<bitset> #include<cmath> #define eps 1e-6 #define INF 0x3f3f3f3f #define PI acos(-1.0) #define ll __int64 #define LL long long #define lson l,m,(rt<<1) #define rson m+1,r,(rt<<1)|1 #define M 1000000007 //#pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; #define Maxn 11 int n,m; int vis[Maxn],va[Maxn],cnt; LL ans; LL gcd(LL a,LL b) { if(a%b==0) return b; return gcd(b,a%b); } LL lcm(LL a,LL b) { return a/gcd(a,b)*b; } void dfs(LL le,int cur,int num) { if(num>cnt||le>m) return ; for(int i=cur;i<=cnt;i++) { LL temp=lcm(le,va[i]); if(num&1) ans+=m/temp; else ans-=m/temp; dfs(temp,i+1,num+1); } } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); while(~scanf("%d%d",&n,&m)) { cnt=0; memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) { int a; scanf("%d",&a); if(!vis[a]) { vis[a]=1; va[++cnt]=a; } } ans=0; for(int i=1;i<=cnt;i++) { ans+=m/va[i]; dfs(va[i],i+1,2); } printf("%lld\n",ans); } return 0; }