莫比乌斯&筛法

题目链接 Sky Code

题意：

给出一个大小为n的集合，求出满足条件的4元子集的个数。
这个条件就是：该四元子集{a,b,c,d} ,满足 gcd(a,b,c,d)=1

思路

第一步算法分析：
☞第一感觉就是容斥原理，原命题等价：
☞记Ai为gcd(a,b,c,d)=i的集合个数
☞ans＝C（n,4）-A2-A3-A5...+(A2x3+A2x5+...)-(A2x3x5...)
☞再一看数据量：1e4 bingo，很小，果断mobius打表直接做了。
☞最后mobius下的公式就是：
☞ans=∑mobius[i]＊Ai
第二步复杂度分析:
☞1e4 下mobius打表忽略不计
☞求Ai 这个是比较常见的思路分两步走
☞1.求出是2，3，4，6，7...的倍数的集合元素个数Si
☞那么Ai＝C ( Si , 4 ).
☞这个求法有两种思路
☞暴力求解

for(int i=0;i<n;i++){
    for(int j=0;j<=data[i];i++){
        if(data[i]%j==0) num[j]++;
    }
}

☞复杂度 O(n ＊ max(data[i])) 对于这里也就1e4 * 1e4估计还是可以的，但正式比赛肯定不行。
☞筛法

        
        for(int i=2;i<=Max;i++){
            for(int j=i;j<=Max;j+=i){
                if(vis[j]) num[i]++;
            }
        }
        

☞复杂度 Maxlg(Max) 这个一般就可以了，还有一种 sqrt(Max)lg(Max)的，我也不是很会写 ，有兴趣的可以加我qq讨论下 844704...
☞2.最后求下c(a,i) 就可以了
☞这个也要预处理 c(n,m)=c(n-1,m-1)+c(n-1,m)
剪枝思考&&debug
☞这个步骤很重要，也是区别1次AC和5次AC的分水岭
☞给出几个简单的剪枝
☞n<4 直接为0
☞Max压缩筛法数据范围
☞debug 核心在于构造边界数据，这点我也是菜鸟
☞分享几个自己当是用到的：
☞c（10000，4）<51e14 longlong ok
☞1e4*ln(1e4)< 1e9(一般算法大于这个基本是出不来的....)

下面给出AC代码：

//
//  main.cpp
//  MSKYCODE - Sky Code
//
//  Created by ccccsober on 6/25/16.
//  Copyright © 2016 cccsober. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <cassert>
#include <string>
#include <sstream>
#include <math.h>
#include <set>
#include <bitset>
#include <vector>
#include <stack>
#include <map>
#include <queue>
#include <deque>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cctype>
#include <complex>
using namespace std;
const int MAX1= 20000  ;
//const int Mod=   ;
const double plus=0.49999999;
const int INF=0x3f3f3f3f;
typedef long long LL;
typedef unsigned long long ULL;
#define M_PI 3.141592653589
int num[MAX1];
LL multi[MAX1][5];
int mobius[MAX1];
int data[MAX1];
bool vis[MAX1];
vector<int> prime;
void Multi(){
    for(int i=0;i<MAX1;i++)
        multi[i][0]=1;
    for(int i=1;i<MAX1;i++){
        for(int j=1;j<5;j++){
            multi[i][j]=multi[i-1][j-1]+multi[i-1][j];
        }
    }
}
void Mobius(){
    memset(vis,0,sizeof(vis));
    mobius[1]=1;
    for(int i=2;i<MAX1;i++){
        if(!vis[i]){
            prime.push_back(i);
            mobius[i]=-1;
        }
        for(int j=0;j<prime.size() && i*prime[j]<MAX1;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j])
                mobius[i*prime[j]]=-mobius[i];
            else{
                mobius[i*prime[j]]=0;
                break;
            }
        }
    }
    
}
void _init(){
    memset(num,0,sizeof(num));
    memset(vis,0,sizeof(vis));
}
int main(int argc, const char * argv[]) {
    freopen("/Users/sperc4/Desktop/input.txt", "r", stdin);
    int n;
    Mobius();
    Multi();
    while(scanf("%d",&n)!=EOF){
        _init();
        int Max=-INF;
        int t;
        for(int i=0;i<n;i++){
            scanf("%d",&t);
            Max=max(Max,t);
            vis[t]=1;
//            for(int j=0;prime[j]<=t;j++){           //这个位置RT了一发
//                if(t%prime[j]) continue;
//                num[prime[j]]++;
//            }
        }
        if(n<4) {cout<<"0"<<endl;continue;}
        
        for(int i=2;i<=Max;i++){
            for(int j=i;j<=Max;j+=i){
                if(vis[j]) num[i]++;
            }
        }
        
        
        
        LL ans=0;
        for(int i=1;i<=Max;i++){
            ans+=(LL)mobius[i]*multi[num[i]][4];
        }
        printf("%lld\n",multi[n][4]+ans);
    }
    return 0;
}