首页 > 代码库 > hdu 3908 Triple(组合计数、容斥原理)
hdu 3908 Triple(组合计数、容斥原理)
Triple
Time Limit: 5000/3000 MS (Java/Others) Memory Limit: 125536/65536 K (Java/Others) Total Submission(s): 1365 Accepted Submission(s): 549
Problem Description
Given many different integers, find out the number of triples (a, b, c) which satisfy a, b, c are co-primed each other or are not co-primed each other. In a triple, (a, b, c) and (b, a, c) are considered as same triple.
Input
The first line contains a single integer T (T <= 15), indicating the number of test cases. In each case, the first line contains one integer n (3 <= n <= 800), second line contains n different integers d (2 <= d < 105) separated with space.
Output
For each test case, output an integer in one line, indicating the number of triples.
Sample Input
1 6 2 3 5 7 11 13
Sample Output
20
Source
2011 Multi-University Training Contest 7 - Host by ECNU
给你n个数，对于其中的任意n个数，a,b,c 要么两两互斥，要么a,b,c两两不互斥......
要你求出满足这一条件的组合数。
分析：
对于任意的三个数，a，b,c 我们知道有这些情况，0对互斥（即两两都不互斥），1对互斥，两对互斥，三对互斥（即两两互斥）。
其后思路与其相同： http://blog.csdn.net/cool_fires/article/details/8681888
代码：
1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 const int maxn=100005; 5 int item[maxn]; 6 int gcd(int a,int b) 7 { 8 if(b==0)return a; 9 return gcd(b,a%b);10 }11 int main()12 {13 int cas,n;14 scanf("%d",&cas);15 while(cas--)16 {17 scanf("%d",&n);18 for(int i=0;i<n;i++)19 scanf("%d",item+i);20 int ans=0;21 for(int i=0;i<n;i++)22 {23 int numa=0,numb=0;24 for(int j=0;j<n;j++)25 {26 if(i!=j)27 {28 if(gcd(item[i],item[j])==1)numa++;29 else numb++;30 }31 }32 ans+=numa*numb;33 }34 printf("%d\n",(n*(n-1)*(n-2)/6)-ans/2);35 }36 return 0;37 }
hdu 3908 Triple(组合计数、容斥原理)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。