前两题是模板题，不讲了。

T3.破解 D-H 协议

T3.破解 D-H 协议

其实这题很暴力，你只需要求出 $g^x \equiv A\bmod p$ 的一个解然后直接算出来 $T$ 即可。

T4.屠龙勇士

每条龙对应的剑是确定的，这里直接用 set 就可以维护了。

那么我们现在就是要解除 $\begin{cases} b_1 x_1 \equiv a_1 \bmod p_1 \\ b_2 x_2 \equiv a_2 \bmod p_2 \\ \cdots \\ b_n x_n \equiv a_n \bmod p_n \end{cases}$ 这个方程。

这个东西只是带了一个系数的 CRT，和原本的差不多。其实只是在一些地方前面添上了几个 $b_i$ 而已，这里就不展开讲了，可以自己手推一下。

T5. 古代猪文

大杂烩！

根据欧拉定理，可以把上面的指数的模数变为 $999911658$。现在重心就变为了怎么求上面那个东西。

这个数很明显就不是是素数了，就不能直接用逆元求解了。但是如果直接用 Lucas 时间可定不行（时间复杂度 $\mathrm O(p \log_p n)$）。那怎么办呢？

我们那么尝试把模数缩小再合并，合并的时候可以CRT求。那么模数分别是 $2,3,4679,35617$。现在我们就利用 Lucas 求就不会有问题了。