单色三角形模型：空间里有n个点，任意三点不共线。每两个点之间都用红色或者黑色线段链接。如果一个三角形的三条边同色，责成这个三角形是单色三角形。对于给定的红色线段列表，找出单色三角形的个数。
分析：对于一个顶点，设他连红线的点又x个，那么它脸黑线的点有(n-1-x)个，那么能组成的三角形有x*(n-1-x)个，因为每个点都会遍历，所以得到的结果会重复算，答案应除2。最终结果是C(n, 3) - sum/2。
hdu-5072
题意，给你n个数，问你有多少对a. b. c 使两两互质，或者两两不互质。
分析：由上我们可以将互质不互质看成红蓝线，那么处理方式就是一样的了。其实就是组合数学和容斥。
ll pri[maxn],pri_num; ll mu[maxn];//莫比乌斯函数值 bool vis[maxn]; void mobius() {//筛法求莫比乌斯函数 pri_num = 0;//素数个数 memset(vis, false, sizeof(vis)); vis[1] = true; mu[1] = 1; for(int i = 2; i <maxn; i++){ if(!vis[i]){ pri[pri_num++] = i; mu[i] = -1; } for(int j=0; j<pri_num && i*pri[j]<maxn ; j++){ vis[i*pri[j]]=true;//标记非素数 if(i%pri[j])mu[i*pri[j]] = -mu[i]; else { mu[i*pri[j]] = 0; break; } } } } int a[maxn]; ll num[maxn], have[maxn]; void solve() { ll n; scanf("%lld", &n); memset(vis, 0, sizeof(vis)); memset(a, 0, sizeof(a)); memset(have, 0, sizeof(have)); memset(num, 0, sizeof(num)); int maxx=0; for (int i=0; i<n; i++) { scanf("%d", &a[i]); vis[a[i]]++; maxx=max(maxx, a[i]); } for (int i=1; i<=maxx; i++) { for (int j=i; j<=maxx; j+=i) num[i] += vis[j]; for (int j=i; j<=maxx; j+=i) { have[j] += mu[i]*num[i]; } } ll ans=0; for (int i=0; i<n; i++) { if (a[i]!=1) { ans += have[a[i]]*(n-1-have[a[i]]); } } ans = n*(n-1)*(n-2)/6 - ans/2; printf("%lld ", ans); } int main() { int t=1; // freopen("in.txt", "r", stdin); scanf("%d", &t); mobius(); for (int T=1; T<=t; T++) { // printf("Case %d: ", T); solve(); } return 0; }