加载中…HDU 3908 Triple 2011 Multi-University Training Contest 7 - Host by ECNU
(2011-08-02 20:30:10)
标签：
hdu3908it |
分类： 杂题 |
题目描述：
给你n个数，问满足条件1或者条件2的a，b，c组合有多少个。
条件1：任意两个互质
条件2：任意两个不互质
解题报告：
比赛时想复杂了。。。
只要统计A[i]:和第i个数互质的有多少个。
和B[i]：和第i个数不互质的有多少个。
那么A[i] * B[i]是包含i的不合法的组合的一个子集。
不难发现，对每个i进行这样的操作，能够覆盖到所有的不满足条件的abc，而且是算了两次。
所以，最后就是C(n,3)- sum/2即可。
代码如下：
if (a
< b) return gcd(b, a);
if (b
== 0) return a;
return
gcd(b, a % b);
scanf("%d", &t);
while(t--)
{
scanf("%d",
&n);
for(int i = 0; i
< n; i++) scanf("%d", &x[i]), A[i] =
B[i] = 0;
for(int i = 0; i
< n; i++)
for(int j = 0; j < n; j++) if (j
!= i)
if
(gcd(x[i], x[j]) == 1) A[i]++;
else
B[i]++;
int ans = n * (n - 1) * (n -
2) / 6, sum = 0;
for(int i = 0; i
< n; i++)
sum += A[i] * B[i];
ans -= sum / 2;
printf("%d\n", ans);
}
给你n个数，问满足条件1或者条件2的a，b，c组合有多少个。
条件1：任意两个互质
条件2：任意两个不互质
解题报告：
比赛时想复杂了。。。
只要统计A[i]:和第i个数互质的有多少个。
和B[i]：和第i个数不互质的有多少个。
那么A[i] * B[i]是包含i的不合法的组合的一个子集。
不难发现，对每个i进行这样的操作，能够覆盖到所有的不满足条件的abc，而且是算了两次。
所以，最后就是C(n,3)- sum/2即可。
代码如下：
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;
int gcd(int a, int b)
{
}
int x[1000], n, t, A[1000], B[1000];
int main()
{
return 0;
}
喜欢
0
赠金笔