\(i\) 以下の整数の中の \(n\) で割ったあまりが \(j\) となる個数は

\[f(i, j) = \begin{cases} 0 & (i < j) \\ \floor{(i-j)/n} + 1 & (i \geq j) \end{cases}\]

である.

よって, 区間 \([l, r]\) の中のあまりが \(j\) となる個数は

\[f(r, j) - f(l-1, j)\]

で求められる.