程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> hdu1796 How many integers can you find 容斥原理

hdu1796 How many integers can you find 容斥原理

編輯：關於C++

Description

Now you get a number N, and a M-integers set, you should find out how many integers which are small than N, that they can divided exactly by any integers in the set. For example, N=12, and M-integer set is {2,3}, so there is another set {2,3,4,6,8,9,10}, all the integers of the set can be divided exactly by 2 or 3. As a result, you just output the number 7.

Input

There are a lot of cases. For each case, the first line contains two integers N and M. The follow line contains the M integers, and all of them are different from each other. 0 Output

For each case, output the number.

Sample Input

12 2
2 3

Sample Output

能被給出的第二行的數整除的數的個數；

sum=被一個整除-被兩個整除+被三個整除-。。。。。。

注意一個他自己本身不算

#include
#include
#include
#include
#include
#include
#include
#include
#include
#pragma comment(linker,/STACK:102400000,102400000)
#define pi acos(-1.0)
#define EPS 1e-6
#define INF (1<<24)
using namespace std;
int m,n,cnt;
int num[20];
int visi[20];
long long int sum;
long long int gcd(long long int a,long long int b) //最大公約數
{
if(b==0)
{
return a;
}
return gcd(b,a%b);
}
long long int lcm(long long int a,long long int b) //最小公倍數
{
return a/gcd(a,b)*b;
}
void solve()
{
int i,flag=0;//記錄有多少個數
long long int t=1,ans;
for(i=0;i {
if(visi[i])
{
flag++;
t=lcm(t,num[i]);
}
}
ans=n/t;
if(n%t==0) ans--;
if(flag%2==1) sum=sum+ans; //奇數加，偶數減
else sum=sum-ans;
}
int main()
{
while(scanf(%d %d,&n,&m)!=EOF)
{
int i,j;
int a;
cnt=0;
sum=0;
for(i=0;i {
scanf(%d,&a);
if(a!=0) num[cnt++]=a;
}
//int m=cnt;
int zhuang=1< for(i=1;i {
int tem=i;
for(j=0;j {
visi[j]=tem&1;
tem=tem>>1;
}
solve();
}
printf(%I64d ,sum);
}
return 0;
}