\(i=0,1,\dots ,N\) に対して累積和 \(s_i = \displaystyle\sum_{j=1}^{i}\dfrac{p_i}{q_i}\) を考えます。ただし \(s_0=0\) です。このとき、次の問題に帰着されます。

\(0\le l\lt r\le N\) を満たす整数の組 \((l,r)\) であって \(s_r-s_l\) が整数であるものの個数を数え上げよ。

\(2\) つの実数の差が整数であることと \(2\) つの実数の小数部分が等しいことは同値です。ただし、実数 \(x\) の小数部分を \(x-\lfloor x\rfloor\) として定めます。

これを用いれば、

与えられたいくつかの実数を、その小数部分によって分類せよ。

という問題を解くことができれば良いことがわかります。

ハッシュを用いましょう。扱う値は有理数であることから、小数部分を \(\bmod M\) で管理することを考えます。ここで \(M\) はとても大きな正整数です。

\(s_i\) を \(\bmod M\) で計算することは簡単ですが、そこには小数部分だけでなく整数部分の情報も入っています。そこで整数部分は浮動小数点数で計算しておき、その値を引くことで \(s_i\) の小数部分を \(\bmod M\) で得ることができます。

ここで問題になるのは次のような点です。

• \(M\) としてどの程度の大きさのものを用意すれば \(\bmod M\) で小数部分が等しいことによって本当に小数部分が等しいことが高確率で保証できるか
• 浮動小数点数で累積和の整数部分が正確に計算できるか

前者を考えます。まず \(M\) をランダムに取れば小数部分は \(\bmod M\) で十分ランダムに分布します。累積和 \(N+1\) 個のうちの全てのペアに対して、小数部分が異なるならば \(\bmod M\) での小数部分も異ならなければなりません。このことから \(M\) として \(10^{18}\) 程度の大きさの値を選べば十分高確率で正答できると見積もれます。そこで \(M\) として \(10^9\) 程度の素数をランダムに \(2\) つ用意して累積和のペアをハッシュとして持てば良いです。

Bonus : \(M\) がわかっている解法なら撃墜するケースを作ることができます。

後者を考えます。累積和の整数部分を浮動小数点数で計算すると、誤差が発生してうまくいかないケースがあります。しかし、あらかじめ累積和に適切な定数 \(c\) を足しておけば、すべての累積和の整数部分が浮動小数点数でもうまく計算できるようになります。実際に累積和を計算して、整数部分を計算する際に誤差が影響しそうならそれを回避するように \(c\) を設定すれば良いです。そもそも累積和 \(\bmod M\) の値が変わってしまうように見えますが、同じ分だけ変わるので問題ありません。

Bonus : 累積和の小数部分は \(10^{-40000}\) 程度まで小さくすることができます。

ハッシュを連想配列などで管理すれば、時間計算量 \(O(N\log N)\) 程度でこの問題を解くことができます。

実装例(C++)