别样的 \(\text{NOI}\) 模拟赛。
\(A\) 十几分钟能写完的随机化都放过去了，\(B\) 题面的代码 \(CE\) 了，\(C\) 边分治的思路仅闪过一瞬就忘了。
A.离散猜数
你说得对，但是
若答案正确，且你的代码使用的询问次数为 \(x\)，std 使用的询问次数为 \(y\)，计算 \(c=\dfrac{x}{y}\)。
若 \(c\le 1\)，得到该测试点 100% 的分数。
否则若 \(c\le 5\)，得到该测试点 75% 的分数。
否则若 \(c\le 20\)，得到该测试点 50% 的分数。
否则，得到该测试点 25% 的分数。
本地随了一下，平均最多随四个数后 \(\gcd\) 就变成 \(1\) 了，写个 \(\text{exgcd}\) 期望得分 \(75\) ，实际得分 \(100\) 。
不会原根，但看到大家基本都是随机过的，悬着的心终于似了。
摆个题解，感觉说的很对啊。
我们希望找到一个 \(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\) 意义下的最小原根后，即可在一次询问内解决问题。
所以明明一次就能解决，随机为什么要给满分。
C.多边形
发现边分治最难的是怎么找到合适的边。
我们选定一条端点为 \((s,t)\) 的边后，由于图是一个凸多边形的三角剖分图，所以位于这条边两侧的点的最短路一定经过 \(s\) 或 \(t\)，以这两个端点为源点分别跑一边最短路，对一个点 \(u\)，记它到两端点最短路为 \(a_u,b_u\)，那么左边一个点 \(u\) 到右边一个点 \(v\) 的最短路为 \(\min(a_u+a_v,b_u+b_v)\)。而 \(a_u+a_v\le b_u+b_v\iff a_u-b_u\le b_v-a_v\)，于是容易在一次排序后统计跨过左右两边的最短路对答案的贡献。
现在唯一的问题是找到合适的边，显然要尽量选把点集均分的边。
总时间复杂度 \(O(n\log^2n)\) 。
标签：le,原根,测试点,pmod,短路,10.19,equiv From： https://www.cnblogs.com/ZepX-D/p/18478103