Yuhang's Blog

桥(洛谷P2685)题解

给定一张无向图, 有边权, 可能有重边和自环. 我们用$p_0$表示原图上从节点$1$到$n$的一条最短路. 对图上的任意一条边$e$, 设$p(e)$是删去边$e$后的从$1$到$n$的最短路, 设$f(e)$是$p(e)$的... Read more

扩展中国剩余定理

考虑$\mathbb{Z}$上的线性同余方程组 $x \equiv a_i \bmod n_i$, 其中$i = 1, .., r$. 则该方程组有解, 当且仅当对于任意$i\not= j$, 都有$a_i \equiv a_j \bmod \text{gcd} (n_i, n_j)$. Read more