hdu1796 How many integers can you find 容斥原理 - c++编程基础

TOP

hdu1796 How many integers can you find 容斥原理

2015-11-21 00:54:34 来源: 作者: 【大中小】浏览:1次

Tags：hdu1796 How many integers can you find 容斥原理

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;
}


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：[LeetCode] Gas Station	下一篇：HDU 2871 Memory Control（线段树..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: