本文主要是介绍HDU 3908 Triple (逆向思维)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://acm.hdu.edu.cn/showproblem.php?pid=3908
题意：给定一个数组，判断数组中这样的三元组的个数：要么三个元素两两互素，要么三个元素两两都不互素。
ans=C(n,3) - 三个数中有一对互素的并且有一对不互素的个数sum
sum怎么算？
对于num[i]，计算与之互素的元素的个数pnum，那么不互素的元素的个数就是n-1-pnum了，对于num[i]而言，不满足条件的三元组个数为pnum*(n-1-pnum)。
注意最后还要除2：比如(2, 3, 4)在处理2的时候算了一次，在处理4的时候也算了一次，但是在处理3的时候，肯定不会出现，因为对3而言，2与3互素，4也与3互素，所以总的来说每个三元组都多算了一次。
完整代码：
/*1015ms,260KB*/#include<cstdio>
const int maxn = 805;int a[maxn];int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}int main()
{int t;scanf("%d", &t);while (t --){int n;scanf("%d", &n);for (int i = 0; i < n; i++) scanf("%d", &a[i]);int ans = 0;for (int i = 0; i < n; i++){int num = 0;for (int j = 0; j < n; j++)if (i != j && gcd(a[i], a[j]) == 1) ++num;ans += num * (n - num - 1);}printf("%d\n", n * (n - 1) * (n - 2) / 6 - ans / 2);}return 0;
}
这篇关于HDU 3908 Triple (逆向思维)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
