有理数を \(\mathrm{mod} \ P\) で扱い、 hash を用意する方針は toam さんのユーザ解説と同じです。 hash として用意する \(P\) の値に関わらず、 \(\sum_{i = l}^r \frac{p_i}{q_i} = X\) が整数なら累積和の差分は \(X \ \mathrm{mod} \ P\) です。ここで、 \(P\) を大きく取ればこれは \(X\) で変わりません。

よって \(P\) を複数取ったとき、ある区間の和が整数なら累積和の hash 間の差分はその区間を始める前と変わりません。正確には \(X\) を足すことで累積和が \(P\) 以上となることは起こりますが、そのような確率は十分低いと予想できます。

これより \(P\) を複数種類用意して累積和の hash が一致するような区間を数え上げればよく 、これは map などを使えば \(O \left( N \left( \log N + \log P \right) \right)\) です。

実装では __int128 を用いて \(P = \{ 2 \times 10^{15} + 21, 2 \times 10^{15} + 77, 2 \times 10^{15} + 81 \}\) としました。