#莫比乌斯函数，容斥定理#POJ 3904 SP4191 Sky Code

本文主要是介绍#莫比乌斯函数，容斥定理#POJ 3904 SP4191 Sky Code，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

给定 $n$ 个数，现在让你求出有多少个四元组，满足这四个数的最大公约数等于1。
$n\leq 10000$ ,每个数 $\leq 10000$ 。
多组询问，对于每个询问回答多少个四元组满足条件

分析

直接等于1很难，可以考虑容斥，就是用全部的方案减去不合法的方案，质因数有奇数个为负，偶数个为正，但是当质因数的指数超过1时会重复，所以无需考虑，细细一想，莫比乌斯函数？？？，嗯答案就是 $\sum_{k=4}^{t}(-1)^{cnt[k]}C_{k}^{4}$

代码

#include <cstdio>
#include <cctype>
#include <cstring>
#define rr register
using namespace std;
const int N=10001;
typedef long long ll; ll c[N]; bool v[N];
int mu[N],prime[1231],cnt[N],tot,n;
inline signed iut(){rr int ans=0; rr char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans; 
}
signed main(){mu[1]=1;for (rr int i=2;i<N;++i){if (!v[i]) prime[++tot]=i,mu[i]=-1;for (rr int j=1;j<=tot&&prime[j]*i<N;++j){v[i*prime[j]]=1;if (i%prime[j]) mu[i*prime[j]]=-mu[i];else break;}}for (rr int i=4;i<N;++i) c[i]=1ll*i*(i-1)*(i-2)/3*(i-3)>>3;while (scanf("%d",&n)==1){memset(cnt,0,sizeof(cnt)); rr ll ans=0;for (rr int i=1;i<=n;++i) ++cnt[iut()];for (rr int i=1;i<N;++i)for (rr int j=i<<1;j<N;j+=i)cnt[i]+=cnt[j];for (rr int i=1;i<N;++i)if (cnt[i]>3) ans=ans+c[cnt[i]]*mu[i];printf("%lld\n",ans);} return 0;
}