CSUSTOJ 你真的会数据结构吗？（质因数分解）

本文主要是介绍CSUSTOJ 你真的会数据结构吗？（质因数分解），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
$a[i]$最多只有30，对应10个素因子，仅考虑这些素因子即可。

考虑题目的$f(n)$，可以发现，$f(n)=2^{cnt}$，$cnt$代表$d$的素因子个数，所以我们只需要维护每个数的素因子个数。相同素因子的数可以合并。

所以完全不需要数据结构，直接用数组维护就好了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <iostream>
#include <map>
#include <string>
#include <set>using namespace std;typedef long long ll;const int mod = 1e9 + 7;
const int maxn = 1e5 + 7;vector<int>G[maxn];
int a[maxn],fa[maxn];
pair<int,int>num[50];
int p[20] = {2,3,5,7,11,13,17,19,23,29}; //10个质数
int s[maxn][40],P[40];pair<int,int> trans(int x) {int res = 1;int cnt = 0;for(int i = 0;i <= 9;i++) {if(x % p[i] == 0) {res *= p[i];cnt++;}}return {cnt,res};
}void init() {P[0] = 1;for(int i = 1;i <= 30;i++) {num[i] = trans(i);P[i] = P[i - 1] * 2;}
}void dfs(int x,int f) {fa[x] = f;for(int i = 0;i < G[x].size();i++) {int v = G[x][i];if(v == f) continue;dfs(v,x);s[x][num[a[v]].second]++;}
}int main() {init();int n;scanf("%d",&n);for(int i = 2;i <= n;i++) {int x,y;scanf("%d%d",&x,&y);G[x].push_back(y);G[y].push_back(x);}for(int i = 1;i <= n;i++) {scanf("%d",&a[i]);}dfs(1,0);int q;scanf("%d",&q);for(int i = 1;i <= q;i++) {int op;scanf("%d",&op);if(op == 1) {int x,y;scanf("%d%d",&x,&y);s[fa[x]][num[a[x]].second]--;a[x] = y;s[fa[x]][num[a[x]].second]++;} else {int x;scanf("%d",&x);if(G[x].size() == 1 && x != 1) {printf("0 0\n");} else {int mi = 1e9,cnt = 0;for(int j = 1;j <= 30;j++) {if(s[x][j]) {if(num[j].first < mi) {mi = num[j].first;cnt = s[x][j];} else if(num[j].first == mi) {mi = num[j].first;cnt = max(cnt,s[x][j]);}}}printf("%d %d\n",cnt,P[mi]);}}}return 0;
}

这篇关于CSUSTOJ 你真的会数据结构吗？（质因数分解）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---