NOJ 2079 Prime （莫比乌斯反演）

本文主要是介绍NOJ 2079 Prime （莫比乌斯反演），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Prime

时间限制(普通/Java):1000MS/3000MS         运行内存限制:65536KByte
总提交:267          测试通过:11

比赛描述
给定n个数,求两两互斥的对数。互斥是指两个数的最大公约数是1

输入
第一行为样例数T(T<=5)
对每个样例，第一行为一个整数n(2=<n<=10^5),代表数的个数。
接下来一行包含n个数，a1,a2,…,an(1<=ai<=10^5)

输出
对于每个样例，在一行输出答案。

样例输入
1
2
2 3

样例输出
1

题目链接：http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=2079

题目分析：先预处理处1e5的莫比乌斯函数，因为mob[i]=1表示i是偶数个素因子的乘积，mob[i]=-1表示i是奇数个素因子的乘积，mob[i]=0表示其他
回到这道题上，首先对于总的集合我任意取出两个数的情况数为C(n,2)即  n * (n - 1) / 2，然后依次减去不满足的情况，即gcd为2的gcd为3的，这里就出问题了，因为如果gcd为6，那就被减了两次，所以要容斥一下，即拿总的情况－gcd只由一个素因子构成的情况＋gcd只有两个素因子构成的情况。。。对于每个gcd值的集合我们可以用一个num数组记录。然后就可以看出莫比乌斯函数的强大了，容斥时对应的正负号其实就是mob数组，比如计算gcd为2的集合时，mob[2]==-1，因此减去 num[2] * (num[2] - 1) / 2，3的时候也是减，6的时候则是加，正好与mob函数的定义吻合

注：因为莫比乌斯函数是积性函数，因此可以用线性筛求得

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
int const MAX = 1e5 + 5;
int p[MAX], cnt[MAX], num[MAX], mob[MAX];
bool prime[MAX];
int pnum, ma, n;void Mobius()   //求解莫比乌斯函数
{pnum = 0;mob[1] = 1;memset(prime, true, sizeof(prime));for(int i = 2; i < MAX; i++){if(prime[i]){p[pnum ++] = i;mob[i] = -1;}for(int j = 0; j < pnum && i * p[j] < MAX; j++){prime[i * p[j]] = false;if(i % p[j] == 0){mob[i * p[j]] = 0;break;}mob[i * p[j]] = -mob[i];}}
}ll cal()
{ll ans = (ll) n * (n - 1) / 2;for(int i = 2; i <= ma ; i++){num[i] = 0;for(int j = i; j <= ma; j += i)num[i] += cnt[j];   //得到gcd为i的集合的元素个数}   for(int i = 2; i <= ma; i++)ans += (ll) mob[i] * num[i] * (num[i] - 1) / 2;return ans;
}int main()
{   Mobius();int T;scanf("%d", &T);while(T--){memset(cnt, 0, sizeof(cnt));ma = 0;scanf("%d", &n);for(int i = 0; i < n; i ++){int tmp;scanf("%d", &tmp);cnt[tmp] ++;ma = max(ma, tmp);}printf("%I64d\n", cal());}
}

这篇关于NOJ 2079 Prime （莫比乌斯反演）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---