题解 SP4191 【MSKYCODE - Sky Code】

· · 题解

我终于见到第一个会用莫比乌斯函数的题了（反演菜鸡QAQ）。

这道题比较适合初学容斥的人做。

传送门

题目大意：给出n个数，求其中任意四个数互质的方案数。（n≤1e4）

“互质”也就要求最大公约数为1，即四个数没有相同的质因子，例如：如果四个数a,b,c,d都是2的倍数，那么它们一定不互质，至于为何一定是质因子，因为它是最简的约数，任何数都能用质因子的次幂之积的形式表达出来且唯一，具体的可以参考一些其它学习资料（如某进阶指南），这里便不再赘述。

总之问题就转化成了从n个数里抽出4个数，使它们没有公共的质因子。即选中4个数后，对于任意一个质因子，都不能整除这4个数的方案数。

因为最多有10000个[1,10000]范围内的数，所以涉及到的质因子可能会与n同级别，直接枚举复杂度爆炸。

对于这种有很多限制的题目，我们可以考虑一下容斥。

既然我们考虑的是对于每一个质因子都不能全部整除四个数，那我们可以反过来考虑一下至少有某些质因子全部整除四个数。至于为什么这样考虑，是因为这是根据容斥原理的公式和内容类比得来的。其实是懒得打公式（逃。

因此，我们能得到如下等式：

每个质因子都不全能整除的方案数=不带限制的总方案数
                            -至少一个质因子全能整除的方案数
                            +至少两个质因子全能整除的方案数
                            -至少三个质因子全能整除的方案数
                            ......以此类推。

这样问题又转化成了如何求至少有某些质因子全部整除四个数的方案数。先求出n个数中所有能被这些质因子之积整除的数的数量，因为从中取任意4个都能满足上述条件，所以直接计算\binom{num}{4}就可以了。

怎么去求数量？暴力枚举质因子的组合然后暴力统计？显然时间并不够用。

其实我们忘记了一个时间复杂度与调和级数有关的求一些数的同一个约数的总个数的方法。那就是枚举约数，然后再在值域内枚举它的倍数，统计它是n个数中多少个数的约数，用调和级数证明这么做的复杂度是O(NlnN)的。

然后我们只需要从所有枚举的约数里，找到需要的约数即可。（质因子分解后每个幂的指数都是1的数），关于容斥系数，可以暴力求质因子个数，然后奇数为正，偶数为负。

但是还记得我们开头说了什么吗？

所有数的统计答案直接乘上对应的莫比乌斯函数再求和即是正确答案！

因为对于质因子幂的指数不为1的数，它的莫比乌斯函数值是0，对于质因子个数是奇数的数，它的莫比乌斯函数值是-1，而对于质因子个数是偶数的数，它的莫比乌斯函数值是1，正好符合我们的要求！

总而言之，我们先预处理出1~10000内所有的莫比乌斯函数，然后对于每组询问先统计约数的个数，然后计算\sum_{i=1}^{max_a}\mu_i \times \binom{cnt_i}{4}即可，别忘了清空数组！

上代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#define N 10005
#define ll long long
using namespace std;
int n,sum[N],maxn,prime[N];
ll ans;
int tag[N],mo[N],vis[N];
void init()
{
    mo[1]=1;
    for(int i=2;i<=N-5;i++)
    {
        if(!vis[i])mo[i]=-1,prime[++prime[0]]=i;
        for(int j=1;prime[j]*i<=N-5&&j<=prime[0];j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j])mo[i*prime[j]]=mo[i]*(-1);
            else break;
        }
    }
}
void clean()
{
    maxn=ans=0;
    memset(tag,0,sizeof(tag));
    memset(sum,0,sizeof(sum));
}
ll C(ll a,ll b)
{
    if(a<b)return 0;
    if(b==0)return 1;
    ll res=1;
    for(ll i=0;i<b;i++)res*=a-i;
    for(ll i=1;i<=b;i++)res/=i;
    return res;
}
int main()
{
    init();
    while(scanf("%d",&n)!=EOF)
    {
        clean();
        for(int i=1,x;i<=n;i++)
            scanf("%d",&x),maxn=max(maxn,x),tag[x]=1;
        for(int i=1;i<=maxn;i++)
            for(int j=i;j<=maxn;j+=i)
                if(tag[j])sum[i]++;
        for(int i=1;i<=maxn;i++)
            ans+=mo[i]*C(sum[i],4);
        printf("%lld\n",ans);
    }
    return 0;
}