莫比乌斯&筛法
题意：
给出一个大小为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;
}
