Coprime （单色三角形+莫比乌斯反演（数论容斥））

这道题，先说一下单色三角形吧，推荐一篇noip的论文《国家集训队2003论文集许智磊》

链接：https://wenku.baidu.com/view/e87725c52cc58bd63186bd1b.html?from=search

单色三角形指的是n个顶点，有n(n-1)条边，很明显是每个点两两相连，那么这样所形成的所有三角形的边假如有两种颜色：红和黑。那么问一共有多少三角形的三边是一种颜色的个数。

，建议看一下那个论文，因为我只能直接给出你结论。下面的数学符号：{...}为概率论中表示事件的符号（集合）,|{...}| 表示集合的元素个数。

如图，可知 |{ 单色三角形事件 } | =|{ 所有三角形 }| - |{ 非单色三角形 }| 很容易得 | { 所有三角形 } | = C³_n=n(n-1)(n-2)/6; 那么就直接把| { 非单色三角形 } |求出来。

如图：非单色三角形有的情况和的情况，但是无疑都存在两个顶点所连接的两个边都是异色。那么，我们就将这个图抽象成n个这样类似的图那么，如果知道顶点 i 的红色边 ai 的话，那么黑色边就是 n-1-ai，那么，| { 包含 i 顶点的非单色三角形 } |=ai(n-1-ai); 那么，由加法原理得 | { 非单色三角形 } | = ∑ai(n-1-ai);

这样就可以计算出，所有单色三角形的个数了。

那么，我们先看看这个题的特性（ai, aj, ak）{i<j<k} S={ 满足两两互质，或者两两不互质 }。是不是相当于边的颜色为红色和为黑色呢？那么，ai 就相当于顶点

假如，我们已经知道了ai 与那些所给的数据不互质的个数 bi 。（我们先说不互质的情况。至于为什么，一会下面理解了莫比乌兹反演就知道了。）

那么，|S|=|{ 所有(ai，aj, ak)的任意组合 }| - |{ !S }|　　　　（!S表示S的反）

还是，把重点放在| {！S} | 上，刚刚，我们是假设已知那些数据与ai不互质的个数bi，但是怎么得到bi就涉及到另一个重大的问题。

莫比乌斯反演——容斥原理。

其实，这道题加深了我个人对莫比乌斯的理解吧。

都知道一般容斥原理的公式，|S1+S2+S3+S4+S5.....+Sk|=∑(-1)^(n-1)∏(Sx...Sy) （不知道的自己百度）

这个公式，用文氏图非常明显，是任何时间（集合）的子集之间的相互关系的一种，当然也是定义讲的好。

那么，数论呢？其实，它也有像一般容斥的公式，它就是莫比乌斯反演。只不过，它的集合就是以所有数为元素的集合，处理的对象很多是（x, y）这样的数对。

回到题上：当转化为gcd（ai，aj）=k，那么，我们可以在数据ai中找出最大值max，得到一个k的范围 [ 1, max]，先记录枚举当数据ai中质数因子为k的个数，记录为 mk。这样就得到了[ 1, max ]为质因子的数的个数{m}。

这时，把 gcd（x， y）！=1 这个拿出来，由x， y的唯一质数分解得，∑|{gcd(x, 1)=1}|-∑| {gcd（x,y）=k} | +∑|{gcd(x, y)=n*m}|-∑|{gcd(x, y)=nmh}|....=∑u(d)F(n/d); （感觉这里写的有些毛病。）

ac代码：

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

#define ll long long

const int maxn = 1e5 + ;

int a[maxn];

int vis[maxn];

int mu[maxn];

int prime[maxn];

void mobius()

{

    mu[] = ;

    int cnt = ;

    for (int i = ; i < maxn; ++i)

    {

        if (!vis[i]){    prime[cnt++] = i;    mu[i] = -;}

        for (int j = ; j < cnt&&prime[j] * i < maxn; ++j)

        {

            vis[prime[j] * i] = ;

            if (i%prime[j] == ){ mu[prime[j] * i] = ; break; }

            mu[prime[j] * i] = -mu[i];

        }

    }

}

int maxx;

ll n, hz[maxn], num[maxn];

void solve()

{

    memset(hz, , sizeof(hz));

    memset(num, , sizeof(num));

    for (int i = ; i <= maxx; ++i)

    {

        for (int j = i; j <= maxx; j += i)        //寻找i的倍数的个数

            num[i] += vis[j];

        for (int j = i; j <= maxx; j += i)

            hz[j] += mu[i] * num[i];

    }

    ll ans = ;

    for (int i = ; i < n; ++i)

    {

        if (a[i] != )

        {

            ans += 1LL*(hz[a[i]]*(n -  - hz[a[i]]));

        }

    }

    ans = n*(n - ) * 1LL * (n - ) /  - ans / ;

    printf("%lld\n", ans);

}

int main()

{

    int t;

    scanf("%d", &t);

    mobius();

    while (t--)

    {

        memset(vis, , sizeof(vis));

        memset(a, , sizeof(a));

        scanf("%lld", &n);

        maxx = ;

        for (int i = ; i < n; ++i)

        {

            scanf("%lld", &a[i]);

            ++vis[a[i]];

            maxx = max(maxx, a[i]);

        }

        solve();

    }

}

巴特西

Coprime （单色三角形+莫比乌斯反演（数论容斥））

最新文章

热门文章