首页 > 代码库 > hdu 5072 Coprime
hdu 5072 Coprime
Coprime
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 56 Accepted Submission(s): 20
Problem Description
There are n people standing in a line. Each of them has a unique id number.
Now the Ragnarok is coming. We should choose 3 people to defend the evil. As a group, the 3 people should be able to communicate. They are able to communicate if and only if their id numbers are pairwise coprime or pairwise not coprime. In other words, if their id numbers are a, b, c, then they can communicate if and only if [(a, b) = (b, c) = (a, c) = 1] or [(a, b) ≠ 1 and (a, c) ≠ 1 and (b, c) ≠ 1], where (x, y) denotes the greatest common divisor of x and y.
We want to know how many 3-people-groups can be chosen from the n people.
Now the Ragnarok is coming. We should choose 3 people to defend the evil. As a group, the 3 people should be able to communicate. They are able to communicate if and only if their id numbers are pairwise coprime or pairwise not coprime. In other words, if their id numbers are a, b, c, then they can communicate if and only if [(a, b) = (b, c) = (a, c) = 1] or [(a, b) ≠ 1 and (a, c) ≠ 1 and (b, c) ≠ 1], where (x, y) denotes the greatest common divisor of x and y.
We want to know how many 3-people-groups can be chosen from the n people.
Input
The first line contains an integer T (T ≤ 5), denoting the number of the test cases.
For each test case, the first line contains an integer n(3 ≤ n ≤ 105), denoting the number of people. The next line contains n distinct integers a1, a2, . . . , an(1 ≤ ai ≤ 105) separated by a single space, where ai stands for the id number of the i-th person.
For each test case, the first line contains an integer n(3 ≤ n ≤ 105), denoting the number of people. The next line contains n distinct integers a1, a2, . . . , an(1 ≤ ai ≤ 105) separated by a single space, where ai stands for the id number of the i-th person.
Output
For each test case, output the answer in a line.
Sample Input
1
5
1 3 9 10 2
Sample Output
4
Source
2014 Asia AnShan Regional Contest
先用容斥求出和a[i] 互质的个数num ，然后不符合条件的 就是 num*(n-1-num);
把所有不符合的加起来/2， 就是所有不符合的组数，最后用总的组数减去不合法的就好了
对于 num 的求法：
先用cnt[i] 表示。因子里面有 i 的数的个数。
对于a[i] ,先分解质因子，然后就可以用容斥求了，具体看代码
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>#include<vector>#include<set>#include<stack>#include<map>#include<ctime>#include<bitset>#define LL long long#define INF 999999#define maxn 500010using namespace std;int cnt[maxn] ,a[maxn] ;vector<int>q;int main(){ int i ,j , n ,m , k , v ; LL ans,sum; int T ,len,u; cin >>T ; while(T--) { scanf("%d",&n) ; for( i =1 ; i <= n ;i++) scanf("%d",&a[i]) ; memset(cnt,0,sizeof(cnt)) ; for( i = 1 ; i <= n ;i++) { for( j = 1 ; j*j <= a[i] ;j++)if(a[i]%j==0) { cnt[j]++ ; if(a[i]/j != j )cnt[a[i]/j]++; } } ans = 0 ; for( i = 1 ; i <= n ;i++) { q.clear(); m = a[i]; for( j = 2 ; j*j <= m ;j++)if(m%j==0) { q.push_back(j) ; while(m%j==0) m /= j ; } if(m != 1) q.push_back(m) ; k = q.size() ; len = (1<<k) ; int hehe=0; sum=0; u=1; for( j = 1 ;j < len ;j++) { hehe=0; u=1; for( v = 0 ; v < k ;v++ ) if((1<<v)&j) { hehe++ ; u *= q[v] ; } if(hehe&1) sum += cnt[u] ; else sum -= cnt[u] ; } if(sum)sum--; ans += sum*(n-1-sum) ; } ans/=2; LL hehe = (LL)n*(n-1)*(n-2)/6 ; printf("%I64d\n",hehe-ans) ; } return 0 ;}
hdu 5072 Coprime
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。