自动搬运

查看原文

来自洛谷，原作者为

	喵仔牛奶 黄昏再美终要黑夜。

搬运于2025-08-24 23:16:46，当前版本为作者最后更新于2025-04-20 13:09:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

闲话：这题是 FAOI R6 原来的 C 题，5.5 交审，然后撞了 5.25 图灵杯的题 :(

Solution

特判掉边权全为 $0$ 的情况。求出所有边权值的 $\gcd$，记为 $D$，将所有边权值除以 $D$。一条路径的真实路径为这种情况下的长度乘以 $D$。

由于一个环走 $z$ 次长度为 $0$，我们可以经过任意一个环任意次（经过一个环 $z$ 次，然后在途中插入另一个环）。记所有环长度和的 $\gcd$ 为 $d$，那么根据裴蜀定理，如果存在一条长度为 $p$ 的路径，一定存在一条长度为 $p\bmod\gcd(d,z)$ 的路径。

考虑求出 $d$。由于 $\gcd(2w_1,2w_2,c\dots,2w_m)=2$，$d\mid 2$。因此，如果存在长度为奇数的环，$d=1$，否则 $d=2$。将长度为偶数的边的两端合并为同一个点，如果不是二分图，说明存在长度为奇数的环。

我们求出了 $d$，考虑询问如何解决。分类讨论：

• $d=1$：此时 $\gcd(d,z)=1$，存在长度为 $0$ 的路径，答案为 $0$。
• $d=2$：此时图为二分图。分类讨论：
  • 若 $x,y$ 在同一部分，它们之间所有路径长度为偶数，模 $\gcd(d,z)$ 显然为 $0$，答案为 $0$。
  • 若 $x,y$ 不在同一部分，它们之间所有路径长度为奇数，若 $\gcd(d,z)=1$，答案为 $0$。否则，路径的真实长度为 $D+2Dx$（$x$ 可以为任意非负整数）。根据裴蜀定理，答案即为 $D\bmod\gcd(2D,z)$。

复杂度 $\mathcal O(n+m+q\log V)$。