http://acm.hdu.edu.cn/showproblem.php?pid=5072

題意：給出 n 個互不相同的數，求滿足以下條件的三元無序組的個數：要么兩兩互質要么兩兩不互質。

思路：根據同色三角形原理求，白書105頁。求它不符合條件的情況數，先對每一個數分解質因子，然后利用容斥求出與這個數不互質的數的個數，那么不符合條件的的情況數加上（x-1）*(n-x); ?x為其它數與這個數不互質的個數。最后總的情況數減去不符合的情況數，剩下的就是答案。再求多少個是這個數的倍數的時候，可以用篩法求出。

1 #include <cstdio> 2 #include <cstring> 3 #include <vector> 4 #include <algorithm> 5 #define maxn 100010 6 using namespace std; 7 8 int t,n; 9 int a[maxn+10]; 10 int num[maxn+10]; 11 int cnt[maxn+10]; 12 vector<int>g; 13 14 int main() 15 { 16 scanf("%d",&t); 17 while(t--) 18 { 19 memset(cnt,0,sizeof(cnt)); 20 memset(num,0,sizeof(num)); 21 scanf("%d",&n); 22 for(int i=0; i<n; i++) 23 { 24 scanf("%d",&a[i]); 25 num[a[i]]++; 26 } 27 for(int i=1; i<=maxn; i++) 28 { 29 for(int j=i; j<=maxn; j+=i) 30 { 31 cnt[i]+=num[j]; 32 } 33 } 34 __int64 ans=0; 35 for(int i=1; i<maxn; i++) 36 { 37 if(num[i]) 38 { 39 int m=i; 40 g.clear(); 41 for(int j=2; j*j<=i; j++) 42 { 43 if(m%j==0) 44 { 45 g.push_back(j); 46 while(m%j==0) m/=j; 47 } 48 } 49 if(m>1) g.push_back(m); 50 int x=(int) g.size(); 51 int cc=0; 52 for(int j=1; j<(1<<x); j++) 53 { 54 int t2=0; 55 int xx=1; 56 for(int k=0; k<x; k++) 57 { 58 if((1<<k)&j) 59 { 60 t2++; 61 xx*=g[k]; 62 } 63 } 64 if(t2%2) cc+=cnt[xx]; 65 else cc-=cnt[xx]; 66 } 67 ans+=(__int64)max(cc-1,0)*(n-cc); 68 } 69 } 70 __int64 t1=(__int64)n*(n-1)*(n-2)/6; 71 printf("%I64d\n",t1-ans/2); 72 } 73 return 0; 74 } View Code

?

轉載于:https://www.cnblogs.com/fanminghui/p/4235248.html

總結

以上是生活随笔為你收集整理的hdu 5072 Coprime的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。