不能整除的个数（c语言）题解

求从 1 到 108 之间不能被给定若干个数中任何一个整除的整数个数。

每组数据第一个数为 n，之后 n 个不大于 1000 的正整数，其中 1 ≤ n ≤ 5。

1 到 108 之间不能被给定的数任何一个整除的数的个数。

3 5 6 8
5 1 2 3 4 5

60000000
0

思路：正常的枚举法是一定会超时的，因此就要换种思路，求出所有可以被输入的数里面任意一个整除的整数的个数。说到这，就与容斥原理有关了，就是要求多个集合的交集。

两个集合的交集为：

三个集合的交集为： 

多个集合的交集： 

 可以理解为，加单个集合的和 减两个集合的和 加三个集合的和 减四个集合的和 以此类推。

此题中，我们把上图中的A,B,C集合换成1到10^8中可以被输入数整除的数的多少(就是10^8除以输入数的结果)，比如说，样例中输入了5，6，8那么按照公式，我们可以得到10^8/5+10^8/6+10^8/8-10^8/30（5和6的最小公倍数）-10^8/40-10^8/24（6和8的最小公倍数）+10^8/120（5和6和8的最小公倍数）结果就是4*10^7,最后再用10^8-4*10^7就是答案。 

同时，我的方法是多重循环去实现Cmn组合数的效果（就如找出4个数里面不同的3个数）（我暂时想不到什么方法不用多重循环可以简便地求出多个集合的交集了。）

代码中有很多注释，如果大家有疑问可以提出来QAQ(代码较长，但其实把公式理解了就简单些）

还有，如果有大佬有更好的方法一定要告诉孩子^-^ 谢谢啦！

#include
#include
#include
int main(){
    long long n;
   while(~scanf("%lld",&n))
{
        long long B[5];
         long long w1=n,w,s1,flag=1,d=0,q=1,s=0,a,b,c,m,w3,w2;
          //w，w2，w3是最小公倍数。w1是n。a,b,c是用于求最小公倍数的
      scanf("%lld",&B[0]);n--; //先输入第一个数
      s1=B[0];                 //s1是全部数的最小公倍数
       s=s+100000000/B[0];    //s就是可以被整除的总个数
       while(n--)
       {   if(B[d]==1)flag=0; //判断输入的数里面有无1
           scanf("%lld",&B[q]); 
            a=s1;b=B[++d];      //在输入数时就把s1求出来
            s=s+100000000/B[q++];
           if(a>b)a^=b^=a^=b;//实现a和b替换
              c=a%b,m=a*b;
           while(c!=0){a=b;b=c;c=a%b;}
           s1=m/b;
       }
      if(flag==0)printf("0n");  //有1的话答案肯定为0
      
      else
 {

  if(w1>=2)    
    { //当输入两个或以上的数时，把公式里面的不同的两个集合的交集求出来
    for(long long j=0;jb)a^=b^=a^=b;
              c=a%b,m=a*b;
              while(c!=0){a=b;b=c;c=a%b;}
              w=m/b;
              s=s-100000000/w;//这里是减
         }
        }
    }
   
  if(w1>=4)  
    { //当输入4个或以上的数时，把公式里面不同的3个集合的交集求出来
     for(long long j=0;jb)a^=b^=a^=b;
                c=a%b,m=a*b;
               while(c!=0){a=b;b=c;c=a%b;}
               w2=m/b;         //注意这里
                for(long long k=i+1;kb)a^=b^=a^=b;
                   c=a%b,m=a*b;
                  while(c!=0){a=b;b=c;c=a%b;}
                   w=m/b;//w就是不同的3个数的最小公倍数
                   s=s+100000000/w;//这里是加
                }
            }

        }
  }
 if(w1==5)   
    {//当输入5个数时，
     for(long long j=0;jb)a^=b^=a^=b;
                c=a%b,m=a*b;
               while(c!=0){a=b;b=c;c=a%b;}
               w2=m/b;   
                for(long long k=i+1;kb)a^=b^=a^=b;
                    c=a%b,m=a*b;
                   while(c!=0){a=b;b=c;c=a%b;}
                   w3=m/b;
                   for(long long y=k+1;yb)a^=b^=a^=b;
                     c=a%b,m=a*b;
                    while(c!=0){a=b;b=c;c=a%b;}
                    w=m/b;
                    s=s-100000000/w;//这里是减
                   }
                }
            }
        }

   }
   //当输入1个数时，无需进行下面这步
   //w1==2时，下面这步已经在上面if(w1>=2)中的语句实现了
  if(w1>2)  s=s+pow(-1,w1+1)*(100000000/s1);
printf("%lldn",100000000-s);
 }
}
return 0;
}