【HDU - 5468】Puzzled Elena（容斥原理，dfs序，数学，素因子分解，有坑）

题干：

Problem Description

Since both Stefan and Damon fell in love with Elena, and it was really difficult for her to choose. Bonnie, her best friend, suggested her to throw a question to them, and she would choose the one who can solve it.

Suppose there is a tree with n vertices and n - 1 edges, and there is a value at each vertex. The root is vertex 1. Then for each vertex, could you tell me how many vertices of its subtree can be said to be co-prime with itself?
NOTES: Two vertices are said to be co-prime if their values' GCD (greatest common divisor) equals 1.

Input

There are multiply tests (no more than 8).
For each test, the first line has a number n (1≤n≤105) , after that has n−1 lines, each line has two numbers a and b (1≤a,b≤n) , representing that vertex a is connect with vertex b. Then the next line has n numbers, the ith number indicates the value of the ith vertex. Values of vertices are not less than 1 and not more than 105 .

Output

For each test, at first, please output "Case #k: ", k is the number of test. Then, please output one line with n numbers (separated by spaces), representing the answer of each vertex.

Sample Input

5 1 2 1 3 2 4 2 5 6 2 3 4 5

Sample Output

Case #1: 1 1 0 0 0

题目大意：

给出一棵树n个点,每个点上有权值。然后求每棵子树中与根节点互质，即gcd(a,b)=1的节点个数。

解题报告：

因为1e5以内的每个数的素因子个数不超过10个，所以可以对于每个数的不互素个数可以在O(10*2^10)内算出来，所以直接dfs序映射成一个序列然后按照题意求就行了。注意题目问的是gcd==1而不是互素，所以1和本身也是gcd==1的，所以val==1的时候需要ans++。

贴一个题解：

该题涉及到一个典型问题.问x与数的集合S中有多少个数不互素。解决办法是将S中所有元素依次进行两个步骤：①将元素进行质因数分解。②将质因数可能产生的乘积的出现次数加1。最后将x进行质因数分解，利用容斥原理求解。具体方案见代码。

容斥原理在OJ中常解决两个典型问题：①求S中有多少个数与x不互素。②求1~m中有多少个数与n不互素。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 2e5 + 5;
vector<int> vv[MAX];
int val[MAX],ans[MAX],num[MAX];
int dfn[MAX],in[MAX],out[MAX],id;
vector<int> fac[MAX];
void db() {
	for(int tar = 1; tar<MAX; tar++) {
		int x = tar;
		for(int i = 2; i*i<=x; i++) {
			if(x%i == 0) {
				fac[tar].pb(i);
				while(x%i==0) x/=i;
			}
		}
		if(x > 1) fac[tar].pb(x);
	}
}
int cal(int n,int tar) {
	int res = 0;
	int upp = 1<<fac[n].size(),up = fac[n].size();
	for(int bit = 1; bit<upp; bit++) {
		int cnt = 0,mul = 1;
		for(int i = 0; i<up; i++) {
			if(bit & (1<<i)) {
				cnt++;
				mul *= fac[n][i];
			} 
		}
		if(cnt & 1) res += num[mul];
		else res -= num[mul];
		num[mul] += tar;
	}
	return res;
}
int dfs(int cur,int rt) {
	int ans1 = cal(val[cur],0);
	int res = 0;
	int up = vv[cur].size();
	for(int i = 0; i<up; i++) {
		int v = vv[cur][i];
		if(v == rt) continue;
		res += dfs(v,cur);
	}
	int ans2 = cal(val[cur],1);
	ans[cur] = res - (ans2 - ans1);
	if(val[cur] == 1) ans[cur]++;
	return res+1;
}
int main()
{
	db();
	int n,iCase=0;
	while(~scanf("%d",&n)) {
		//init
		id=0;
		for(int i = 1; i<MAX; i++) num[i] = 0;
		for(int i = 1; i<=n; i++) vv[i].clear(),ans[i]=0;
		for(int a,b,i = 1; i<=n-1; i++) {
			scanf("%d%d",&a,&b);
			vv[a].pb(b);vv[b].pb(a);
		} 
		for(int i = 1; i<=n; i++) scanf("%d",val+i);
		dfs(1,-1);
		printf("Case #%d:",++iCase);
		for(int i = 1; i<=n; i++) printf(" %d",ans[i]); 
		printf("\n");	
	} 
	return 0 ;
}