We consider bitwise. Specifically, we solve the problem for each \(k = 0,1, \ldots 29\):

• Find the number of integers between \(1\) and \(N\) whose remainder divided by \(M\) is \(R\) and \(2^k\)s place is \(1\) in binary?

The answer to the original problem is obtained as the sum of the answers to the problem above for all \(k\).

Here, for a positive integer \(A\), the following three propositions are equivalent:

• the \(2^k\)s place of \(A\) is \(1\) in binary;
• \(2^k \leq (A \bmod 2^{k+1}) < 2^{k+1}\); and
• \([\frac{A+2^k}{2^{k+1}}]-[\frac{A}{2^{k+1}}]=1\).

Therefore, we can use the last form to find the count using “floor sum.”

Since we can find the count in an \(O(\log N)\) time for each \(k\), the complexity for a single test case is \(O((\log N)^2)\).