2024.10.19总结
本文于 github 博客同步更新。
A：
考虑随便取一个数 \(v\)，用一次询问问出 \(t=\log_g v\)。
我们希望找到一个 \(x\) 使得 \(v^x\equiv g\pmod p\)，也即 \(g^{tx}\equiv g\pmod p\iff tx\equiv 1\pmod {p-1}\)。于是，我们希望找到的 \(v\) 使得 \(t\) 与 \(p-1\) 互质即可。
由原根的相关知识我们知道，这样的 \(v\) 就是 \(\pmod p\) 意义下的原根。于是找到 \(\pmod p\) 意义下的最小原根后，即可在一次询问内解决问题。
B：
没改。
C：
边分治。
假设我们现在钦定了一条边，那么这条边一定将图划分为两部分，而且从一部分中的点 \(a\) 到另一部分中的点 \(b\) 一定经过这条边的端点之一。
设两端点为 \(l,r\)，那么 \(dis_{a,b}=\min(dis_{a,l}+dis_{l,b},dis_{a,r}+dis_{r,b})\)，而 \(a_u+a_v\le b_u+b_v\iff a_u-b_u\le b_v-a_v\)，排一遍序即可统计跨过这条边的答案。
考虑每次找到左右两部分边数最接近的边，不断分治即可，时间复杂度为 \(\mathcal O(n\log^2n)\)。