How many integers can you find

Time Limit: 12000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4249 Accepted Submission(s):
1211

Problem 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<N<2^31,0<M<=10, and the
M integer are non-negative and won’t exceed 20.

Output

For each case, output the number.

Sample Input

12 2
2 3

Sample Output

题意：给n个数字，最大不会超过20的非负数，0忽略它可以。给你一个数字M，

问1-M-1中，有多少个数字能被这n数字中任何一个整除（只要满足其中一个能整除就行）。统计个数输出。

思路：容斥，简单容斥。一开始做zoj的一道题，果断数据太水，方法是不对的也能ac。

原来的思路是这样的，对n个数字，筛选掉ai倍数的数字，然后就容斥，但是明显这样的数据有问题

4 6，这样容斥后得到的结果是4 6 -24，不对的，应该是4 6 -12，所以应该是 4 6 -（4*6）/gcd（4，6）

略坑略坑。

 #include<iostream>

 #include<stdio.h>

 #include<cstring>

 #include<cstdlib>

 using namespace std;

 bool Hash[];

 int f[],len,qlen;

 __int64 Q[];

 int gcd(int a,int b)

 {

     if(a<)a=-a;

     if(b<)b=-b;

     if(b==)return a;

     int r;

     while(b)

     {

         r=a%b;

         a=b;

         b=r;

     }

     return a;

 }

 void solve(__int64 m)

 {

     qlen = ;

     Q[]=-;

     for(int i=;i<=len;i++)

     {

         int k=qlen;

         for(int j=;j<=k;j++)

         Q[++qlen]=-*(Q[j]*f[i]/gcd(Q[j],f[i]));

     }

     __int64 sum = ;

     for(int i=;i<=qlen;i++)

     sum = sum+m/Q[i];

     printf("%I64d\n",sum);

 }

 int main()

 {

     int m,x;

     __int64 n;

     while(scanf("%I64d%d",&n,&m)>)

     {

         n=n-;

         memset(Hash,false,sizeof(Hash));

         for(int i=;i<=m;i++)

         {

             scanf("%d",&x);

             Hash[x]=true;

         }

         for(int i=;i<=;i++)

         {

             if(Hash[i]==true)

             for(int j=i+i;j<=;j=j+i)

             if(Hash[j]==true) Hash[j]=false;

         }

         len = ;

         for(int i=;i<=;i++)if(Hash[i]==true) f[++len]=i;

         solve(n);

     }

     return ;

 }

秒客网

HDU How many integers can you find 容斥

How many integers can you find

相关文章