网易笔试：求所有子树因子个数
题目具体不记得了，事后写的题解，感兴趣可以交流
主要是用到唯一分解定理和回溯算法，处理出每个节点的质因子列表，向上合并
// 测试样例5
1 2
1 3
2 4
2 5
1 2 3 4 5
#include <iostream>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long ll;
unordered_map<int, unordered_set<int> > G; //树
const int maxn = 5e4+5;
const ll mod = 1e9+7;
ll ans[maxn]; //答案
unordered_map<int, int> value; // 节点i的值
unordered_map<int, unordered_map<int, int>* > factors; //每个节点所代表的子树的乘积的质因子列表
unordered_map<int, int>* dfs(int u){
unordered_map<int, int>* mp = new unordered_map<int, int>();
int cur = value[u];
// 计算当前节点u的质因子
while(cur > 1){
for(int i=2; i<=cur; i++){ //可以用质数打表优化一下
if( (cur % i) == 0){
(*mp)[i]++;
cur /= i;
}
}
}
for(auto x : G[u]){
auto ret = factors[x] ? factors[x] : dfs(x); //记忆化搜索
for(auto x : *ret){ //合并到根节点
(*mp)[x.first] += x.second;
}
}
ll num = 1;
// 打印每个节点的质因子情况 质因子 : 数量
// cout<<"u = "<<u<<endl;
// for(auto x : *mp){
// cout<<x.first<<" : "<<x.second<<endl;
// }
for(auto x : *mp){
num *= (x.second+1);
num %= mod;
}
ans[u] = num;
return factors[u] = mp;
}
int main(){
int n,u,v,x;
cin>>n;
for(int i=1; i<=n-1; i++){
cin>>u>>v;
G[u].insert(v);
}
for(int i=1; i<=n; i++) {
cin>>x;
value[i] = x;
}
dfs(1);
for(int i=1; i<=n; i++) delete factors[i];
for(int i=1; i<=n; i++) cout<<ans[i]<<" ";
cout<<endl;
return 0;
}
投递柠檬微趣等公司10个岗位 >
