問題を bit ごとに分解して考えます。すなわち、\(k = 0,1, \ldots 29\) に対して以下の問題を解きます。

• \(1\) 以上 \(N\) 以下の整数であって、\(M\) で割った余りが \(R\) になるもののうち、二進表記したときに \(2^k\) の位が \(1\) となるものの個数を求めよ。

すべての \(k\) に対する上の問題の答えを足し合わせることで、本問題の答えを得ることができます。

ここで、正整数 \(A\) に対して

• \(A\) を二進表記したときに \(2^k\) の位が \(1\)
• \(2^k \leq (A \bmod 2^{k+1}) < 2^{k+1}\)
• \([\frac{A+2^k}{2^{k+1}}]-[\frac{A}{2^{k+1}}]=1\)

の \(3\) つは同値です。

したがって、条件を一番下の形に言い換えることによって floor sum を用いて答えを求めることができます。

各 \(k\) に対して \(O(\log N)\) の計算量で答えを求めることができるので、\(1\) つのテストケースにつき計算量は \(O((\log N)^2)\) です。