容斥原理——uva 10325 The Lottery

首先推荐一篇介绍容斥原理很好的博客http://www.cppblog.com/vici/archive/2011/09/05/155103.html

题意：求1~n中不能被给定m个数中任意一个数整除的数的个数。

思路：n-sum(能被整除的个数)

明显用容斥原理：如10 - 能被2整除的数的个数 - 能被3整除的数的个数 + 能被6整除的数的个数

20-能被2整除的数的个数-能被4整除的数的个数+能被4整除的数的个数（2,4的最小公倍数）

加上或减去的是(n/某种组合的最小公倍数)

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #include<memory.h>

 #include<cstdlib>

 #include<vector>

 #define LL long long int

 using namespace std;

 const int MAXN=;

 const double eps=1e-;

 const int inf=0x3f3f3f3f;

 int n,m;

 long long p[];

 long long gcd(long long a,long long b)

 {

     return b ? gcd(b,a%b):a;

 }

 long long lcm(long long a,long long b)

 {

     long long tmp=gcd(a,b);

     return a/tmp*b;

 }

 int main()

 {

     while(~scanf("%d%d",&n,&m))

     {

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

         {

         scanf("%lld",&p[i]);

         }

         int sum=;

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

         {

             LL mult=;

             int ones=;

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

             {

                 if(i&(<<j))

                 {

                     mult=lcm(mult,p[j]);

                     if(mult>n)

                         break;

                     ones++;

                 }

             }

             if(mult>n)

                 continue;

             if(ones%)

                 sum+=n/mult;

             else

                 sum-=n/mult;

         }

         printf("%d\n",n-sum);

     }

     return ;

 }

巴特西

容斥原理——uva 10325 The Lottery

最新文章

热门文章