10325 - The Lottery
The Sports Association of Bangladesh is in great problem with their latest lottery ‘Jodi laiga Jai’. There
are so many participants this time that they cannot manage all the numbers. In an urgent meeting they
have decided that they will ignore some numbers. But how they will choose those unlucky numbers!!!
Mr. NondoDulal who is very interested about historic problems proposed a scheme to get free from
this problem.
You may be interested to know how he has got this scheme. Recently he has read the Joseph’s
problem.
There are N tickets which are numbered from 1 to N. Mr. Nondo will choose M random numbers
and then he will select those numbers which is divisible by at least one of those M numbers. The
numbers which are not divisible by any of those M numbers will be considered for the lottery.
As you know each number is divisible by 1. So Mr. Nondo will never select 1 as one of those M
numbers. Now given N, M and M random numbers, you have to find out the number of tickets which
will be considered for the lottery.
Input
Each input set starts with two Integers N (10 ≤ N < 2
31) and M (1 ≤ M ≤ 15). The next line will
contain M positive integers each of which is not greater than N.
Input is terminated by EOF.
Output
Just print in a line out of N tickets how many will be considered for the lottery.
Sample Input
10 2
2 3
20 2
2 4
Sample Output
3
10
题解：容斥，题意是买彩票，在1~N里面找幸运数字，幸运数字与m个数字分别互质，因为互质，所以想到容斥，sum每次加上与lcy不互质的个数，在减去与lcy1,lcy2的最小公倍数不互质的个数。。。。依次。。。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define mem(x,y) memset(x,y,sizeof(x))
typedef long long LL;
LL gcd(int a,int b){return b==0?a:gcd(b,a%b);}
LL m[20];
int N,M;
vector<int>p;
LL rc(){
LL sum=0,lrc;
for(int i=1;i<(1<<M);i++){
p.clear();
for(int j=0;j<M;j++){
if(i&(1<<j)){//1<<j
p.push_back(m[j]);
}
}
lrc=p[0];
for(int j=1;j<p.size();j++)lrc=lrc*p[j]/gcd(lrc,p[j]);
if(p.size()&1)sum+=N/lrc;
else sum-=N/lrc;
}
printf("%lld\n",N-sum);
}
int main(){
while(~scanf("%d%d",&N,&M)){
for(int i=0;i<M;i++)scanf("%lld",m+i);
rc();
}
return 0;
}