給一棵樹，樹上每個(gè)節(jié)點(diǎn)有一個(gè)權(quán)值，有兩個(gè)操作，RAND操作查詢u的子樹乘積是多少以及有多少因數(shù)，SEED操作把節(jié)點(diǎn)u乘上v

n，q <= 1e5。數(shù)值小于等于1e9，最大的質(zhì)因數(shù)不超過13

組隊(duì)訓(xùn)練和隊(duì)友一起寫的，寫到頭昏，代碼也是合力完成的，我數(shù)學(xué)幾乎為0，數(shù)學(xué)部分感謝隊(duì)友@lllrj抬一手

?

思路：首先由于乘積的值過大，線段樹不能直接維護(hù)權(quán)值，考慮到查詢的是因數(shù)個(gè)數(shù)，所以線段樹直接維護(hù)2,3,5,7,11,13的指數(shù)，乘一個(gè)數(shù)就是把這個(gè)數(shù)質(zhì)因數(shù)分解再單點(diǎn)更新，查詢就是區(qū)間求和，乘積用快速冪計(jì)算，至于因數(shù)的個(gè)數(shù)由唯一分解定理可知，把一個(gè)數(shù)分解質(zhì)因數(shù)變成(x1^n1)*(x2^n2)*(x3^n3)......的形式，因數(shù)的個(gè)數(shù)就是(n1+1)*(n2+1)*(n3+1).....然后兩個(gè)結(jié)果都要對(duì)1e9+7取模，比賽時(shí)后一個(gè)結(jié)果忘記取模浪費(fèi)了快一個(gè)小時(shí)。。。

建樹的話就是按dfs序建樹，也是個(gè)常見套路，參見HDU-3974。需要注意按dfs序建樹之后不能直接用編號(hào)的權(quán)值去建（比如a【3】不一定在線段樹【3,3】這個(gè)點(diǎn)上），所以是先建樹，輸入的時(shí)候做更新

?

AC代碼：217ms，29.4MB

1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<iostream> 5 #include<vector> 6 #include<queue> 7 #include<cmath> 8 #include<set> 9 #define lid id<<1 10 #define rid id<<1|1 11 #define INF 0x3f3f3f3f 12 #define LL long long 13 #define debug(x) cout << "[" << x << "]" << endl 14 using namespace std; 15 const int maxn = 1e5+5; 16 int b[]={2,3,5,7,11,13}; 17 int d[maxn][6]={0}; 18 void cal(int x, int *d) 19 { 20 for(int i = 0;i < 6 ;i++){ 21 while(x%b[i]==0)x/=b[i],d[i]++; 22 } 23 } 24 const int mx = 1e5+10; 25 const int mod = 1e9+7; 26 int L[mx], R[mx], p[mx]; 27 struct tree{ 28 int l, r; 29 int p[6]; //2,3,5,7,11,13 30 int lazy[6]; 31 }tree[mx<<2]; 32 vector<int> G[mx]; 33 int cnt; 34 LL Ans[6] = {0}; 35 36 LL qpow(LL x, LL n){ //x^n 37 LL res = 1; 38 while (n > 0){ 39 if (n & 1) res = res*x%mod; 40 x = x*x % mod; 41 n >>= 1; 42 } 43 return res; 44 } 45 46 void push_up(int id){ 47 for (int i = 0; i < 6; i++) 48 tree[id].p[i] = tree[lid].p[i]+tree[rid].p[i]; 49 } 50 51 void build(int l, int r, int id){ 52 tree[id].l = l; 53 tree[id].r = r; 54 for (int i = 0; i < 6; i++) tree[id].p[i] = 0; 55 if (l == r) return; 56 int mid = (l+r) >> 1; 57 build(l, mid, lid); 58 build(mid+1, r, rid); 59 } 60 61 void dfs(int u){ 62 L[u] = ++cnt; 63 int len = G[u].size(); 64 for (int i = 0; i < len; i++){ 65 int v = G[u][i]; 66 dfs(v); 67 } 68 R[u] = cnt; 69 } 70 71 void upd(int c, int id, int *x){ 72 if (tree[id].l == c && tree[id].r == c){ 73 for (int i = 0; i < 6; i++) 74 tree[id].p[i] += x[i]; 75 return; 76 } 77 int mid = (tree[id].l + tree[id].r)>>1; 78 if (c <= mid) upd(c, lid, x); 79 else upd(c, rid, x); 80 push_up(id); 81 } 82 83 void query(int l, int r, int id){ 84 if (tree[id].l == l && tree[id].r == r){ 85 for (int i = 0; i < 6; i++) 86 Ans[i] += tree[id].p[i]; 87 return; 88 } 89 int mid = (tree[id].l + tree[id].r)>>1; 90 if (r <= mid) query(l, r, lid); 91 else if (mid < l) query(l, r, rid); 92 else { 93 query(l, mid, lid); 94 query(mid+1, r, rid); 95 } 96 } 97 98 int main(){ 99 int n, u, v, a, q; 100 cnt = 0; 101 scanf("%d", &n); 102 for (int i = 1; i < n; i++){ 103 scanf("%d%d", &u, &v); 104 G[u].push_back(v); 105 p[v] = u; 106 } 107 for (int i = 0; i < n; i++){ 108 if (!p[i]) { 109 dfs(i); 110 break; 111 } 112 } 113 build(1, n, 1); 114 for (int i = 0; i < n; i++){ 115 scanf("%d", &a); 116 cal(a,d[i]); 117 upd(L[i], 1, d[i]); 118 } 119 scanf("%d", &q); 120 while (q--){ 121 char s[10]; 122 int d2[6] = {0}; 123 scanf("%s%d", s, &a); 124 if (s[0] =='R'){ 125 memset(Ans, 0, sizeof Ans); 126 query(L[a], R[a], 1); 127 LL ans = 1; 128 LL num = 1; 129 for (int i = 0; i < 6; i++){ 130 //debug(Ans[i]); 131 num = (num*qpow(b[i], Ans[i]))%mod; 132 ans = ans*(Ans[i]+1)%mod; 133 } 134 printf("%lld %lld\n", num, ans); 135 } 136 else { 137 int c; 138 scanf("%d", &c); 139 cal(c, d2); 140 upd(L[a], 1, d2); 141 } 142 } 143 return 0; 144 } View Code

?

賽后微調(diào)（并沒有什么改變）：202ms，27MB

1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<iostream> 5 #include<vector> 6 #include<queue> 7 #include<cmath> 8 #include<set> 9 #define lid id<<1 10 #define rid id<<1|1 11 #define INF 0x3f3f3f3f 12 #define LL long long 13 #define debug(x) cout << "[" << x << "]" << endl 14 using namespace std; 15 16 int b[] = {2, 3, 5, 7, 11, 13}; 17 const int mx = 1e5+10; 18 const int mod = 1e9+7; 19 int L[mx], R[mx], p[mx]; 20 struct tree{ 21 int l, r; 22 int p[6]; 23 int lazy[6]; 24 }tree[mx<<2]; 25 vector<int> G[mx]; 26 int cnt = 0; 27 LL Ans[6] = {0}; 28 29 void cal(int x, int *d){ 30 for(int i = 0; i < 6 ; i++){ 31 while(x % b[i] == 0){ 32 x /= b[i]; 33 d[i]++; 34 } 35 } 36 } 37 38 LL qpow(LL x, LL n){ //x^n 39 LL res = 1; 40 while (n > 0){ 41 if (n & 1) res = res*x%mod; 42 x = x*x % mod; 43 n >>= 1; 44 } 45 return res; 46 } 47 48 void push_up(int id){ 49 for (int i = 0; i < 6; i++) 50 tree[id].p[i] = tree[lid].p[i]+tree[rid].p[i]; 51 } 52 53 void build(int l, int r, int id){ 54 tree[id].l = l; 55 tree[id].r = r; 56 for (int i = 0; i < 6; i++) tree[id].p[i] = 0; 57 if (l == r) return; 58 int mid = (l+r) >> 1; 59 build(l, mid, lid); 60 build(mid+1, r, rid); 61 } 62 63 void dfs(int u){ 64 L[u] = ++cnt; 65 int len = G[u].size(); 66 for (int i = 0; i < len; i++){ 67 int v = G[u][i]; 68 dfs(v); 69 } 70 R[u] = cnt; 71 } 72 73 void upd(int c, int id, int *x){ 74 if (tree[id].l == c && tree[id].r == c){ 75 for (int i = 0; i < 6; i++) 76 tree[id].p[i] += x[i]; 77 return; 78 } 79 int mid = (tree[id].l + tree[id].r)>>1; 80 if (c <= mid) upd(c, lid, x); 81 else upd(c, rid, x); 82 push_up(id); 83 } 84 85 void query(int l, int r, int id){ 86 if (tree[id].l == l && tree[id].r == r){ 87 for (int i = 0; i < 6; i++) 88 Ans[i] += tree[id].p[i]; 89 return; 90 } 91 int mid = (tree[id].l + tree[id].r)>>1; 92 if (r <= mid) query(l, r, lid); 93 else if (mid < l) query(l, r, rid); 94 else { 95 query(l, mid, lid); 96 query(mid+1, r, rid); 97 } 98 } 99 100 int main(){ 101 int n, u, v, a, q; 102 scanf("%d", &n); 103 for (int i = 1; i < n; i++){ 104 scanf("%d%d", &u, &v); 105 G[u].push_back(v); 106 p[v] = u; 107 } 108 for (int i = 0; i < n; i++){ 109 if (!p[i]) { 110 dfs(i); 111 break; 112 } 113 } 114 build(1, n, 1); 115 for (int i = 0; i < n; i++){ 116 int d[6] = {0}; 117 scanf("%d", &a); 118 cal(a, d); 119 upd(L[i], 1, d); 120 } 121 scanf("%d", &q); 122 while (q--){ 123 char s[10]; 124 scanf("%s%d", s, &a); 125 if (s[0] == 'R'){ 126 memset(Ans, 0, sizeof Ans); 127 query(L[a], R[a], 1); 128 LL ans = 1, num = 1; 129 for (int i = 0; i < 6; i++){ 130 num = (num*qpow(b[i], Ans[i]))%mod; 131 ans = ans*(Ans[i]+1)%mod; 132 } 133 printf("%lld %lld\n", num, ans); 134 } 135 else { 136 int c; 137 int d2[6] = {0}; 138 scanf("%d", &c); 139 cal(c, d2); 140 upd(L[a], 1, d2); 141 } 142 } 143 return 0; 144 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/QAQorz/p/9501783.html

總結(jié)

以上是生活随笔為你收集整理的Gym-101466K Random Numbers（线段树，数学，唯一分解定理）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。