CF1835D

原题

翻译

好题！图论用数论的解法真的很巧妙

首先注意读题，要恰好等于\(k\)，因为我看错了

这题有没有边权都是可以做的，为了使这个做法更具普遍性，我们假设原题有边权

可以发现对于满足条件的点对\((x,y)\)至少要满足他们在一个强联通分量内，所以我们可以在每一个强联通分量内计算答案

对于这个强联通分量内的\(q\)个环，把他们的环长分别记作\(len_i\)，则由裴蜀定理可知，定义\(d=\gcd_{i=1}^q{len_i}\)，则对与\(d | s\)，我们一定可以构造出长为\(s\)的答案

但看到这个数据范围，我们肯定不能直接暴力计算所有环的长度，于是我们考虑通过别的方法求解\(d\)

我声称，对于一正整数\(p\)，\(p|d\)的充要条件是找到一个数组\(dis_i\)满足对于原图所有的边\((u,v,w)\)，满足\(dis_v-dis_u \equiv w (\mod p)\)

下面证明其充要性：

• 充分性：

  对于原图的某一个环，记其上所有边的编号所构成的集合为\(S\)，则必有\(\sum_{i \in S}{w_i} \equiv \sum_{i \in S}{(dis_v-dis_u)} \equiv 0 (\mod p)\)即保证了\(p|len\)

• 必要性：

  考虑构造证明，对于这个强联通图建任意一棵生成树，对于树边\((u,v,w)\)，我们令\(dis_v=dis_u+w\)

  对于某一个返祖边，我们可以用类似于充分性的证法证明此构造满足条件

  对于某一个横叉边，它如果只和树边结合是无法生成环的，但如果加入返祖边，我们可以通过以下操作构造“反向边”：

  对于一条边\((u,v,w)\)，我们想构造其反向边\((v,u,-w)\)。由于图强联通，所以我们可以找到任意一条\(v \rightarrow u\)的路径，这时显然形成了一个环，从\(v\)开始绕这个环\(p-1\)次，再走\(v \rightarrow u\)的路径走到\(u\)点，容易得到走过路径长度\(dist(v,u) \times p+w \times (p-1) \equiv -w (\mod p)\)

  于是我们通过这种方法构造了一个经过横叉边的环，通过类似于证明充分性的方法可以证明此构造合法；

  前向边证法类似于横叉边

根据以上证明我们可以构造出数组\(dis_i\)，这个数组在\(\mod p\)下成立是\(p|d\)的充要条件，因此\(d = \gcd_{i=1}^{m}{(dis_v - dis_u - w)}\)

求出\(d\)后不难发现对于点对\((x,y)\)成为答案的条件是\(dis_x - dis_y \equiv dis_y - dis_x \equiv k (\mod d)\)

容易知道要么\(k \equiv 0 (\mod d)\)，要么\(k \equiv \frac{d}{2} (\mod d)\)

如果不满足条件，直接输出0即可；否则我们可以开一个桶记录之前出现过的所有\(dis_x \mod d\)

总复杂度\(O(n+m)\)