HDU-5072 Coprime(容斥原理，同色三角形)

矫情吗；* 2022-06-09 01:11 163阅读 0赞

Coprime HDU - 5072

--------------------

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.  
**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 ≤ 10 5), denoting the number of people. The next line contains n distinct integers a 1, a 2, . . . , a n(1 ≤ a i ≤ 10 5) separated by a single space, where a i 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

题意：给你n个数，从这n个数中找出3个数，问这三个数两两互质或者这三个数两两不互质的情况有多少种。

思路：这道题的原型就是同色三角形，三个数也可以理解为三对数，三个数只可能有一下四种情况：  
1，三对全部互质  
2，两对互质一对不互质  
3，两对不互质一对互质  
4，三对全部不互质。  
那么我们要求1和4，也可以用总数减去2和3。总数就是C（n，3），即n\*(n-1)\*(n-2)/6。  
那么现在的问题就转化成了如何求2和3。

我们发现2和3一定会有一对互质和一对不互质，不妨令a, b互质，b, c不互质。于是我们可以枚举b来统计答案。在除了b自己的所有数中，要么与b互质，要么与b不互质。假设n个数中有x个与b不互质的数，那么b对答案的贡献就是(x - 1) \* (n - x)。注意这里的求出答案之后要除以2，这是因为如果a, c互质，那么可以交换b, c的位置；如果a, c不互质，那么可以交换a, b的位置，每个答案都被计算了两遍。

所以现在问题又转化成了如何求n个数中有多少个与b不互质的数。  
为了不超时，我们需要提前打表，这个地方需要一种特别巧妙的处理，我们把每个数在这n个数中有多少个数是它的倍数给存下来。然后利用容斥原理来求有多少个与b不互质的数。然后答案就出来了。

#include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <cstring>
    using namespace std;
    typedef long long LL;
    const int maxn = 111111;
    
    //filter prim
    int prim[maxn], isprim[maxn];
    int primnum = 0;
    void initprim() {
    	memset(isprim, -1, sizeof isprim);
    	isprim[0] = isprim[1] = 0;
    	prim[primnum++] = 2;
    	for (int i = 4; i<maxn; i += 2) {
    		isprim[i] = 0;
    	}
    	for (int i = 3; i<maxn; i += 2) {
    		if (isprim[i]) {
    			prim[primnum++] = i;
    			for (int j = i + i; j<maxn; j += i) {
    				isprim[j] = 0;
    			}
    		}
    	}
    }
    
    //get factor
    int has[maxn];
    int factor[maxn][6];
    int factornum[maxn];
    void getfactor() {
    	for (int num = 2; num<maxn; num++) {
    		int n = num, cnt = 0;
    		for (int i = 0; i<primnum; i++) {
    			if (isprim[n]) {
    				factor[num][cnt++] = n;
    				break;
    			}
    			if (n%prim[i] == 0) {
    				factor[num][cnt++] = prim[i];
    				while (n%prim[i] == 0) {
    					n /= prim[i];
    				}
    			}
    		}
    		factornum[num] = cnt;
    	}
    }
    
    // count the number of factors of every number
    int num[maxn], cntExtend[maxn];
    void factorExtend(int len) {
    	memset(cntExtend, 0, sizeof cntExtend);
    	for (int i = 1; i<maxn; i++) {
    		for (int j = i; j<maxn; j += i) {
    			if (has[j])
    				cntExtend[i]++;
    		}
    	}
    }
    
    //for every single factor in each number, find out how many numbers is not co-prime with it
    LL solve(int len) {
    	LL re = 0;
    	for (int i = 0; i<len; i++) {
    		int n = num[i];
    		if (n == 1) continue;
    		int facnum = factornum[n];
    		LL sum = 0;
    		for (int k = (1 << facnum) - 1; k>0; k--) {
    			int mul = 1, b = 0;
    			for (int j = 0; j<facnum; j++) {
    				if ((1 << j) & k) {
    					mul *= factor[n][j];
    					b ^= 1;
    				}
    			}
    			if (b) {
    				sum += cntExtend[mul] - 1;
    			}
    			else {
    				sum -= cntExtend[mul] - 1;
    			}
    		}
    		re += (sum)*(len - 1 - sum);
    	}
    	return re;
    }
    
    int main() {
    	//    freopen("data.in","r",stdin);
    	int T, n, x;
    	initprim();
    	getfactor();
    	scanf("%d", &T);
    	while (T--) {
    		scanf("%d", &n);
    		memset(has, 0, sizeof has);
    		for (int i = 0; i<n; i++) {
    			scanf("%d", &x);
    			has[x]++;
    			num[i] = x;
    		}
    		factorExtend(n);
    		LL ans = (LL)n*(n - 1)*(n - 2) / 6 - solve(n) / 2;
    		printf("%I64d\n", ans);
    	}
    
    }