# 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.

## The 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.

## The 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.

## The Output

Just print in a line out of N tickets how many will be considered for the lottery.

```10 2
2 3
20 2
2 4
```

## Sample Output

```3
10
```
```
Md. Kamruzzaman

```

```#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

typedef long long ll;
int n,m,a[20];

ll gcd(ll a,ll b){
return b>0 ? gcd(b,a%b):a;
}

int main(){
while(scanf("%d%d",&n,&m)!=EOF){
int ans=0;
vector <int> v;
for(int i=0;i<m;i++){
scanf("%d",&a[i]);
if(a[i]>0) v.push_back(a[i]);
}
m=v.size();
for(int i=1;i<(1<<m);i++){
int cnt=0;
ll x=1;
for(int t=0;t<m;t++){
if(i&(1<<t)){
cnt++;
x=x*v[t]/gcd(x,v[t]);
}
}
if( cnt&1 ) ans+=(n)/x;
else ans-=(n)/x;
}
cout<<n-ans<<endl;
}
return 0;
}
```

## UVA 11014 - Make a Crystal(容斥原理)

UVA 11014 - Make a Crystal 题目链接 题意:给定一个NxNxN的正方体,求出最多能选几个整数点.使得随意两点PQ不会使PQO共线. 思路:利用容斥原理,设f(k)为点(x, y, z)三点都为k的倍数的点的个数(要扣掉一个原点O).那么全部点就是f(1),之后要去除掉共线的,就是扣掉f(2), f(3), f(5)..f(n).n为素数.由于这些素数中包括了合数的情况,而且这些点必定与f(1)除去这些点以外的点共线,所以扣掉.可是扣掉后会扣掉一些反复的.比方f(6)在f

## UESTC - 1544 当咸鱼也要按照基本法 组合数学 容斥原理

http://acm.uestc.edu.cn/#/problem/show/1544 考虑一下2.2.2这样的情况.答案应该是n / 2 如果只选一个的情况下,对答案的贡献是正的,但是这里有三个,也就是我们统计了3 * n / 2,统计多了. 那么对于任选两个数的情况,有三种,(2, 2) * 3,分别都是不同位置的2, /**************************************/ 我做的时候是发现,先讨论只有 2.2的情况,也就是只有两个数的时候,ans = 0,这个时候

## Topcoder SRM 144 DIV 1

BinaryCode 模拟 题意是:定义串P,Q,其中Q[i]=P[i-1]+P[i]+P[i+1],边界取0,并且P必须是01串.现在给你Q,让你求出P. 做法是:枚举第一位是1还是0,然后就可以推到出P[i]=Q[i-1]-P[i-1]-P[i-2],需要注意一下边界就好. Lottery 组合数学 题意是:给你四种买彩票,将他们的中奖概率排序,这四种彩票都是从1到a中取b个数字,第一种是随便取,第二种是选取的必须是有序的,第三种是选取的必须是不同的,第四种是选取的必须是有序且不同的. 做法