CF1515G Phoenix and Odometers 題解

Codeforces

Luogu

給定一張有向圖，\(q\) 次詢問，每次詢問是否存在一個經過 \(v\) 的環，滿足路徑長 \(\equiv s\pmod t\)。

奶到 \(\gcd\) 了，可能再想一步就想通了，但是停下了，有點可惜。

考慮一個環肯定存在于一個強連通分量裡，而每個強連通分量都可以構造一個環經過所有點，是以每個強連通分量答案都一樣。

是以首先 <code>tarjan</code> 縮點，然後對每個強連通分量求答案。

對于每個強連通分量，很顯然能否就與它所有環 \(\gcd\) 的答案有關了，設這個東西是 \(w\)。

設路徑長為 \(l\)，那如果 \(l\bmod\gcd(s,w)\) 不為 \(0\)，必然不行，否則根據裴蜀定理一定可行。

然後我們隻需要統計所有環的 \(\gcd\) 就行了。

直接搞一個 \(\text{dfs}\) 序，然後對于每條非樹邊加入成環大小即可。

證明略，感性了解一下發現是對的，證明詳見洛谷題解區。

點選檢視不好看代碼