【数字染色题解】

前言

考场时看做完大部分人做的题以后随便点开了一道题，没想到是到防 AK 题，但是看一眼，容斥？ 不好求，我求出 的不就行了，然后我感觉我可以 A 掉，所以就在疯狂写 DP ,统计各个其前缀，和当前 位置互质的个数，DP 柿子我都想好了，结果上个厕所发现，没法去重啊！当时人都崩了，也没有在做题。

正解

看到清新的题解后感觉自己想难了，根本没有往莫比乌斯函数去想。

我们考虑若一个序列中只用 以及他的倍数，那么我们的 必然 ，考虑选择方案 。
我们再考虑 ，貌似也是这样，在考虑其他素因子，貌似还是这样。

但是不难想到会用重复， 会被 算两边，考虑去重。

根据容斥原理，奇加偶减，所以我们需要对偶数个不同的素因子的乘积产生的选择方案贡献减去，奇数的加上去，这不就是莫比乌斯函数吗，这和容斥原理推欧拉函数的思想是一样的，当时没有看出来也真是 sb 。

那么答案就是：

不得不说，用莫比乌斯函数做过的题还真不多，这题目确实不戳！

#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long    
using namespace std;
const int B=2e5+10;
const int mod=1e9+7;
int read() {int x;scanf("%lld",&x);return x;}
int n,m,k;
int mu[B+10];
int pre[B+10];
int cnt;
int vis[B+10];
void pro()
{
    mu[1]=1;
    for (int i=2;i<=B;i++)
    {
        if (!vis[i]) pre[++cnt]=i,mu[i]=1;
        for (int j=1;j<=cnt && pre[j]*i<=B;j++)
        {
            vis[pre[j]*i]=1;
            if (i%pre[j]==0) break;
            else mu[pre[j]*i]=-mu[i];
        }
    }
}
int a[B+10];
int siz[B+10];
int mul(int a,int b)
{
    int res=1;
    while (b)
    {
        if (b&1) res=res%mod*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
signed main()
{
    pro(); 
    n=read();
    for (int i=1;i<=n;i++) 
    {
        a[i]=read();
    }
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j*j<=a[i];j++)
        {
            if (j*j==a[i])
            {
                siz[j]++;
            }
            else if (a[i]%j==0)
            {
                siz[j]++;
                siz[a[i]/j]++;
            }
        }
    }
    int ans=0;
    for (int i=2;i<=B;i++)
    {
        ans=(ans%mod+mu[i]*(mul(2,siz[i])-1)%mod+mod)%mod;
    }
    printf("%lld",(ans%mod+mod)%mod);
}