poj 3904 Sky Code【容斥原理】

点击打开链接

Description

Input

Output

Sample Input

4
2 3 4 5 
4
2 4 6 8 
7
2 3 4 5 7 6 8

Sample Output

1 
0 
34

解题思路：本题可以先计算n个数字选四个总共有多少种选法，然后减去公约数不是1的。把共同具有某一素因子的数字划分到同一个集合，属于统一集合的四个数最大公约数一定大于1，如果四个数字不同时属于任何集合则最大公约数一定为1。用总的组合数减去那些四个数字同时被同一个集合包括了的组合数，所得结果即为最终答案。但是这些一个四个数字的组合可能同时属于若干个集合，因此需要在这些集合之间进行容斥原理，以求每个需要被减去的四个数字的组合都恰好被减掉一次。

首先，先将算法流程说一下，原理后面会有
Step 1：预处理，求组合数C（n，4），存于数组p中，方便下面运算！
Step 2：组合素数，用prime数组记录由m(m<=5)个素数相乘所得数的素因子
Step 3：读入当前数为a，将a分解为质因数形式，注意每个质因数只被记录一次
例如：  182=2*7*13 ———> m=3 so，相加
            2=2 ——>m=1 so，相加
            91=7*13 ——>m=2 so，相减
            注意12=2^2*3等这种是B=p1^k1*p2^k2+...这种有质因数指数不为一的合数记录不同因子的个数
            12=2*2*3 则 12会被分为2*3，多余的2被消去了，因此m=2；
Step 4：将分出的素数进行组合，并统计每种的方案数
例如：12=2^2*3——>12=2*3——>cnt[2]++,cnt[3]++,cnt[6]++
Step 5：处理之后，ans赋值为0
Step 6：for i 2-->10000
            if （m==奇数）    ans:=ans+C(cnt[i],4)
            else    ans:=and-C(cnt[i],4);
Step 7：输出ans
原理：首先考虑一个问题，1000以内6,7,8,9的倍数有多少个？答案是
1000div6+1000div7+1000div8+1000div9
-1000div(6*7)-1000div(6*8)-1000div(6*9)-1000div(7*8)-1000div(7*9)-1000div(8*9)
+1000div(6*7*8)+1000div(6*8*9)+1000div(7*8*9)
-1000div(6*7*8*9)
这是容斥原理的一个最简单的应用，类比这道题，Step3到4其实将每个数a的不重复约数记录了下来，
有公共约数的四个数的方案要从ans中减去，多减的要加上
显然m为奇时要减，m为偶时要加，这和”1000以内6,7,8,9的倍数有多少个？“这个问题奇偶是反的，
由于a最大为10000，所以m最大可以有5 (2*3*5*7*11<10000,2*3*5*7*11*13>10000)
  此表格解释利用2进制查找素因子组合

#include<iostream>
#include<stdio.h>
#include<string.h>
#define MAX 10005
using namespace std;
int cnt[MAX],num[MAX],prime[5];//数组不必过大，5个单位即可
long long  p[MAX]={0}; //必须用大整数
void Solve(int  n){
    int i,j,tol=0,k,sum;
    for(i=2;i*i<=n;i++){ //计算素因子个数
        if(n%i==0)
            prime[tol++]=i;
        while(n%i==0)//去重复因子
            n/=i;
    }
    if(n!=1) prime[tol++]=n;    //如果本身就是大于n开方的素数，需要加一，这点不要忘记
    for(i=1;i<(1<<tol);i++){  //总共有1~2^tol-1个组合
        k=1,sum=0;
        for(j=0;j<tol;j++)//巧妙利用二进制来查找到所有素因子组合构成的数
            if(i&(1<<j)){
                k*=prime[j];
                sum++;
            }
        cnt[k]++; //记录含有因子K的数的个数,比如n=30,则cnt[2]++,cnt[3]++,cnt[5]++;
                                            //cnt[6]++,cnt[10]++,cnt[15]++;cnt[30]++;
        num[k]=sum;//记录k中含有素因子的个数 num[2]=1,num[3]=1,num[5]=1,num[6]=2,
    }                                       //num[10]=2,num[15]=2,num[30]=3,
}
int main(){
   int m,n;
   long long i;
   for(i=4;i<MAX;i++)        //先打表，提高效率，i<4时p[i]为0；
        p[i]=i*(i-1)*(i-2)*(i-3)/24;
   while(~scanf("%d",&n)){
       memset(cnt,0,sizeof(cnt));
       for(i=0;i<n;i++){
           scanf("%d",&m);
           Solve(m);        //求解其素因子，并统计相关数据
       }
       long long ans=0;
       for(i=0;i<MAX;i++)
           if(cnt[i]>=4)//剪枝，必须大于等于四
               if(num[i]&1) //假如含有素因子个数为奇数，则加上；否则减去
                    ans+=p[cnt[i]];
               else
                    ans-=p[cnt[i]];
       cout<<p[n]-ans<<endl; //最后用总的减去不符合的四元组个数
   }return 0;
}