首页 > ACM题库 > HDU-杭电 > HDU 3908-Triple-最小生成树-[解题报告]HOJ
2015
04-14

HDU 3908-Triple-最小生成树-[解题报告]HOJ

Triple

问题描述 :

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.

输入:

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.

输出:

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.

样例输入:

1
6
2 3 5 7 11 13

样例输出:

20

/*
分析:
    参考别人的思路才做出来的。
  摘:
    解题报告:
只要统计a[i]:和第i个数互质的有多少个。
和b[i]:和第i个数不互质的有多少个。
那么a[i] * b[i]是包含i的不合法的组合的一个子集。
不难发现,对每个i进行这样的操作,能够覆盖到所有的不满足条件的abc,而且是算了两次。
所以,最后就是C(n,3)- sum/2即可。

                                                        2012-04-18
*/

#include"stdio.h"
#include"string.h"
int cor_prime(int a,int b)
{
	int t;
	if(a<b)
	{
		t=a;
		a=b;
		b=t;
	}
	t=a%b;
	while(t)
	{
		a=b;
		b=t;
		t=a%b;
	}
	if(b==1)
		return 1;
	else
		return 0;
}


int main()
{
	int i,l;
	int T;
	int n;
	int num[801];
	int count;
	int sum;
	int total;
	int flag1[801];
	int flag2[801];
	scanf("%d",&T);
	while(T--)
	{
		memset(flag1,0,sizeof(flag1));
		scanf("%d",&n);
		for(i=0;i<n;i++)
			scanf("%d",&num[i]);


		for(i=0;i<n-1;i++)
			for(l=i+1;l<n;l++)
			{
				if(cor_prime(num[i],num[l]))
				{
					flag1[i]++;
					flag1[l]++;
				}
			}
		for(i=0;i<n;i++)
			flag2[i]=n-1-flag1[i];


		sum=0;
		for(i=0;i<n;i++)
			sum+=flag1[i]*flag2[i];
		sum/=2;
		total=n*(n-1)*(n-2)/6;


		count=total-sum;


		printf("%d\n",count);
	}
	return 0;

}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/ice_crazy/article/details/7474856


  1. 这个方法是错的,不信你试试:
    20 5
    1 A:9
    1 A:9
    1 A:9
    1 A:6
    1 A:4
    正确答案应该是19,这个答案是18

  2. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。