两道题似乎都涉及了一个经典模型：
在一张有向图上，给定起点 \(s\) 和终点 \(t\)，询问 \(s\) 到 \(t\) 与 \(t\) 到 \(s\) 是否均存在一条长度 \(=L\) 的路径（\(L\) 是一个 \(\ge n^3\) 的数）。
首先 \(s\) 与 \(t\) 必须在同一个 SCC 内（考场上没看到互相可达直接以为不可做）。
考虑取出这个 SCC 的任意一颗生成树，则有定理：
设所有非树边 \((u,v)\) 的 \(|dep_u+1-dep_v|\) 的 \(\gcd\) 为 \(g\)，则 \(\forall x \in \text{SCC},\exists L, \mathrm{s.t.} \forall l \ge L \and g|l\)，存在包含 \(x\)、长为 \(l\) 的环。
证明：设当前所有包含 \(x\) 的环的 \(\gcd\) 为 \(g\)。
- 若所有 \(dep_u+1 \equiv dep_v \pmod{g}\)，显然从 \(x\) 出发，每走一步在模 \(g\) 意义下深度一定 \(+1\)，回到 \(x\) 时肯定长度为 \(g\) 的倍数。
- 若存在 \(dep_u+1 \not\equiv dep_v \pmod{g}\)，则存在 1 个只经过 1 条这种边的环，这个环的长度显然不是 \(g\) 的倍数。根据裴蜀定理，\(g\) 可以变为 \(\gcd(g,l)\)（\(l\) 为这个环的长度），可以变得更小。
根据证明过程，可以扩展这个定理：
\(\forall x,y \in \text{SCC},\exists L, \mathrm{s.t.} \forall l \ge L \and l \equiv dep_y-dep_x \pmod {g}\)，存在以 \(x\) 为起点、以 \(y\) 为终点、长为 \(l\) 的路径。
证明过程类似。
标签：ABC306G,dep,SCC,pmod,ge,CF1835D,思考,forall,equiv From： https://www.cnblogs.com/acceptedzhs/p/17490777.html