数学。数学。串串。
A
\(\varphi(n) = n\cdot \prod \frac{p_i - 1}{p_i}\)。
又因为每次迭代的 \(k\) 不变，所以最终答案的质因子只有初始 \(n,k\) 可达的质因子。
知周所众，\(\varphi\) 函数迭代是 \(O(\log n)\) 次降为 \(1\) 的。所以 \(n\) 造成的影响在 \(O(\log n)\) 次之后消失，后面的是 \(k\) 的贡献，每一个 \(k\) 贡献相同，所以后面的答案就是等比数列。
直接暴力模拟求 \(\varphi\) 质因子的指数变化。然后求个 \(O(\log n)\) 次后面变化量就不变了。
fun fact: 在 \(n < 998244353\) 的范围下可以取暴力次数 \(\min(t, 7)\) 通过本题。
B
行列式是可以差分的。
对行列式差分，原操作转化为 \(A_{i, i} \gets A_{i, i} + 1, A_{j + 1, j + 1} \gets A_{j + 1, j + 1} + 1, A_{i, j + 1} \gets A_{i, j + 1} - 1, A_{j + 1, i} \gets A_{j + 1, i} - 1\)。
不难（？）想到矩阵树定理，则操作相当于加一条 \((i, j + 1)\) 的边，最后求生成树数量。
由题意非树边最多 \(300\) 条，将非树边涉及点拿出来建虚树（最多 \(1200\) 个点），虚树上的边的选的方案是 \(1\)，不选的方案数是 \(w\)。统一除以 \(w\)，选的方案是 \(\frac{1}{w}\)，不选的方案是 \(1\)。再把非树边加上，矩阵树定理求出的答案再乘上 \(\prod w\)。
C
改题率最低的一集。
每次重建 SAM 暴力跑 40pts 跑路了。