传送门：点击打开链接
题意：给你一棵树，根节点为1
有2种操作，第一种是给u节点所在的子树的所有节点的权值+x
第二种是询问，假设v是子树u中的节点，有多少种质数满足av?=?p?+?m·k
其中p<m
思路：首先用DFS序，把树弄成线段树来表示，这种做法十分常见就不多讲了
因为m<=1000,我们用bitset保存av%m的值
每次对子树增加权值的时候，只需要修改懒惰标记，来记录增加的大小
然后直接把bitset利用位运算来完成循环移动就行了。
这道题只要能熟练运用bitset，对DFS序的线段树有一定的了解，应该是没很大问题的。
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<bitset>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define fuck(x) cout<<"["<<x<<"]"
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;const int MX = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int M = 1005;
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1int n, m, Q;
int DL[MX], DR[MX], DFN;
int A[MX], B[MX], sum[MX << 2];
bitset<M>stu[MX << 2], temp, pr;
int Head[MX], erear;
struct Edge {int v, nxt;
} E[MX * 2];void edge_init() {erear = 0;memset(Head, -1, sizeof(Head));
}
void edge_add(int u, int v) {E[erear].v = v;E[erear].nxt = Head[u];Head[u] = erear++;
}
bool prime_is(int x) {for(int i = 2; i * i <= x; i++) {if(x % i == 0) return false;}return true;
}
void prime_init() {pr = 0;for(int i = 2; i < m; i++) {if(prime_is(i)) pr.set(i);}
}
void DFS(int u, int f) {DL[u] = ++DFN;B[DFN] = A[u];for(int i = Head[u]; ~i; i = E[i].nxt) {int v = E[i].v;if(v == f) continue;DFS(v, u);}DR[u] = DFN;
}
void push_up(int rt) {stu[rt] = stu[rt << 1] | stu[rt << 1 | 1];
}
void func_right(int rt, int x) {stu[rt] = (stu[rt] << x) | (stu[rt] >> (m - x));
}
void push_down(int rt) {if(sum[rt]) {sum[rt << 1] += sum[rt]; sum[rt << 1] %= m;sum[rt << 1 | 1] += sum[rt]; sum[rt << 1 | 1] %= m;func_right(rt << 1, sum[rt]);func_right(rt << 1 | 1, sum[rt]);sum[rt] = 0;}
}
void build(int l, int r, int rt) {sum[rt] = 0;if(l == r) {stu[rt].reset();stu[rt].set(B[l] % m);return;}int m = (l + r) >> 1;build(lson); build(rson);push_up(rt);
}
void add(int L, int R, int x, int l, int r, int rt) {if(L <= l && r <= R) {sum[rt] = (sum[rt] + x) % m;func_right(rt, x);return;}int m = (l + r) >> 1;push_down(rt);if(L <= m) add(L, R, x, lson);if(R > m) add(L, R, x, rson);push_up(rt);
}
bitset<M> query(int L, int R, int l, int r, int rt) {if(L <= l && r <= R) {return stu[rt];}int m = (l + r) >> 1;push_down(rt);bitset<M> ret;if(L <= m) ret |= query(L, R, lson);if(R > m) ret |= query(L, R, rson);return ret;
}int main() {//FIN;while(~scanf("%d%d", &n, &m)) {DFN = 0;edge_init(); prime_init();for(int i = 1; i <= n; i++) {scanf("%d", &A[i]);}for(int i = 1; i <= n - 1; i++) {int u, v;scanf("%d%d", &u, &v);edge_add(u, v);edge_add(v, u);}DFS(1, -1);build(1, n, 1);scanf("%d", &Q);while(Q--) {int op, a, b;scanf("%d%d", &op, &a);if(op == 1) {scanf("%d", &b);add(DL[a], DR[a], b % m, 1, n, 1);} else {temp = query(DL[a], DR[a], 1, n, 1);printf("%d\n", (int)((temp & pr).count()));}}}
}