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 ?nd out the number of tickets which will be considered for the lottery.
Input Each input set starts with two Integers N (10 ≤ N < 231) 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
#include<bits/stdc++.h>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define read(x,y) scanf("%d%d",&x,&y)#define root l,r,rt
#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define ll long long
ll gcd(ll x,ll y) {return y?gcd(y,x%y):x;}
const int maxn =505;
const int mod=1e6+7;
/*
题目大意:给定n和m个数，
求1到n中不被m集合中任意一个数整除的数的个数。典型容斥原理，
枚举组合子集，然后计数。
但有一个细节需要注意，即要除的应该是子集数的最小公倍数，
并且不超出n，（可能会报数据，但是好像不加也过了）。*/int n,m;
ll divi[20];int main()
{while(scanf("%d%d",&n,&m)!=EOF){ll ans=0;for(int i=0;i<m;i++) scanf("%lld",&divi[i]);for(int i=0;i<(1<<m);i++){ll cnt=1,mark=0;for(int j=0;j<m;j++) if(i&(1<<j)){if(n/cnt) cnt=cnt*divi[j]/gcd(cnt,divi[j]);///细节，但是不加判定好像也能过mark++;}if(mark&1) ans-=n/cnt;else ans+=n/cnt;}printf("%d\n",ans);}return 0;
}