题解：CF1845F Swimmers in the Pool
InQueue
·
·
题解
首先把 (l,t) 变成 (\dfrac12,\dfrac t{2l})，可以证明答案不变。
此时，速度为 a,b（a\neq b）的两人在 t_0 时刻相遇，当且仅当 t_0(a+b)\in \mathbb{Z} 或 t_0(a-b)\in \mathbb{Z}。
令集合 S := \left\{ x\mid \exists1\le i<j\le n,v_i+v_j=x\text{ or }\left|v_i-v_j\right|=x \right\}。可以用 FFT / NTT 求出 S。
我们枚举互质的 (i,j) 表示时间 t_0=\dfrac ji：
ANS &= \sum_{i:\exists x\in S,i|x}\sum_{j\perp i,0<\frac ji\le t}1
\\ &= \sum_{i:\exists x\in S,i|x}\sum_{1\le j\le ti}[j\perp i]
\\ &= \sum_{i:\exists x\in S,i|x}\sum_{1\le j\le ti}\sum_{d|i,d|j}\mu(d)
\\ &= \sum_{i:\exists x\in S,i|x}\sum_{d|i}\mu(d)\sum_{1\le j\le ti,d|j}1
\\ &= \sum_{i:\exists x\in S,i|x}\sum_{d|i}\mu(d)\left \lfloor \dfrac{ti}d \right \rfloor
\end{aligned}
这样直接按着式子枚举即可，总时间复杂度 O(V\log V)。
CF 提交记录。