A

\(n\) 是偶数，\(a,b,c\) 都是素数，平方不改变奇偶性，则 \(a,b,c\) 中有一个偶数或三个偶数，但偶素数只有一个，所以不妨令 \(a=2\)，枚举 \(b\leq \sqrt n\) 就可以算出 \(c\)。需要判断 \(b,c\) 是否是素数，可以用线性筛或是埃氏筛做到这点。为了避免常数过大，最好只枚举 \(b\) 为素数的情况。复杂度 \(O(T\sqrt n)\)。

B

考虑最优策略一定是先放至少出现一次的数，再放出现至少两次的数，以此类推，可以解决 \(q=1\) 的情况。

于是答案只和每个元素 \(x\) 的出现次数 \(f_x\) 有关，当 \(x\) 第 \(i\) 次在 \(a'\) 中出现时，\(a'\) 这个前缀的众数恰好出现 \(i\) 次，于是 \(x\) 的贡献是 \(1+2+\dots+f_x=\frac{f_x(f_x+1)}{2}\)。维护桶 \(f\) 更新答案即可。\(O(n+q)\)。

C

\(n\) 小的时候直接暴力 \(O(n^3)\)，\(k\leq 10\) 需要统计的区间只有 \(O(kn)\) 个也可以暴力用一些数据结构统计区间乘积，\(m\) 是质数的时候可以用逆元+前缀和的方法统计。\(k=n\) 做法和正解一致，边界更少。

统计区间信息常常使用分治，处理 \([l,r]\) 区间时把贡献分为完全在 \([l,mid]\)，完全在 \((mid,r]\) 和在 \([l,r]\) 内且跨过 \(mid,mid+1\) 的三类区间，前两类递归处理，只需要考虑第三类。

如果没有 \(k\) 的限制，从 \(mid+1\) 到 \(r\) 做前缀积再前缀和得到 \(g\)，则 \(g_x\) 代表 \((mid,y]\)，其中 \(y\leq x\) 的所有区间乘积的和，于是我们从 \(mid\) 向 \(l\) 枚举统计区间的左端点 \(L\)，发现右端点的范围在 \((mid,\min(r,L+k-1)]\)，这样就可以使用 \(g\) 得到需要统计的信息了。

\(O(n\log n)\)。

D

对于一个给定的序列 \(a\)，要想计算它的权值，可以从头开始找到最短前缀满足 \(\gcd=1\) 删除然后继续做，容易证明这样是最优的。

据此设计 dp，我们希望能够满足每次切出来的一段都是极短的 \(\gcd=1\) 的前缀，那么设 \(dp_{i,j}\) 表示考虑长度为 \(i\) 的前缀，删掉所有极短 \(\gcd=1\) 的前缀后，剩余部分的 \(\gcd=j\) 的方案数，答案就是 \(\sum dp_{i,1}\times K^{n-i}\)，因为后 \(n-i\) 个元素任意，并且当前结尾部分可以贡献 \(1\) 的权值。为了满足极短，\(dp_{i,1}\) 不应该参与后续转移，而是直接移动到 \(dp_{i,0}\) 表示开启一个空段。

这样可以写出 \(dp_{i,j}\to dp_{i+1,\gcd(j,k)}\)，枚举 \(k\) 做这个的复杂度是 \(O(nK^2)\) 或 \(O(nK^2\log K)\)。

考虑优化，记 \(g_{i,j}=\sum_{k\in [1,K],j|k} dp_{i,k}\)，从 \(dp_{i-1}\) 转移过来，则有 \(g_{i,j}=\lfloor \frac{K}{j}\rfloor\times \sum_{k\in[1,K],j|k}dp_{i-1,k}\)，即 \(a_i\) 在 \(j\) 的倍数中任选一个，这样的转移是 \(O(K\log K)\) 一轮的。有了 \(g\) 的辅助，\(dp_{i,j}=g_{i,j}-\sum_{j<k\leq K,j|k}dp_{i,k}\)，\(dp_{i,0}\) 的转移特殊处理，复杂度同上。于是复杂度变为 \(O(nK\log K)\)，可以通过。

E

\(M\) 是质数时可以 dsu on tree 做做。颜色数 \(\leq 10\) 可以对每个颜色分别贡献到每个点上。

\(M\) 是合数的时候没有逆元可以用了，不妨考虑我们要求的东西的结构，即每个颜色有个权值，求所有仅在子树外出现的颜色的权值乘积。不妨考虑对每个颜色选择一个代表点，将代表点的点权设置为该颜色的强度，其它点的点权为 \(1\)，则通过 dfn 我们可以做到求子树外的点的权值乘积。为了满足题意，求点 \(u\) 的答案时需要满足 \(u\) 子树里出现过的颜色的代表点都在 \(u\) 子树内，这是容易实现的：初始任意分配代表点，然后在 dfs 过程中，处理完点 \(u\) 的时候，将颜色 \(c_u\) 的代表点换为 \(u\) 并统计点 \(u\) 的答案，此时最近访问的 \(sz_u\) 个点就是 \(u\) 子树中的点，那么这些点一定代表了 \(u\) 子树里的全部颜色，此时子树外的权值乘积就是点 \(u\) 的答案。单点修改，求区间乘积，可以用线段树解决。

\(O(n\log n)\)。