[AtCoder] ABC 090 D – Remainder Reminder

問題

方針

\( K = 0 \) のとき

このとき、\( N \) 以下の全ての正の整数の組 \( (a, b)\) が条件を満たすので、\( N^2 \) が答えとなります。

\( K \neq 0 \) のとき

任意の整数 \( x \) に対して、\( 0 \leq x \bmod b \leq b – 1 \) が成り立つので、\( b \) の値の範囲は、

\[ K + 1 \leq b \leq N\]

となります。ここで、\( a = 0 \) を認めて考えます。実際に \( a \bmod b \) を計算すると以下のようになります。

\begin{array}{c|ccc}
\hline
a & 0 & 1 & 2& \cdots & b – 1 & b & 1 & 2 & \cdots\\
\hline
a \bmod b & 0 & 1 & 2 & \cdots & b – 1 & 0 & 1 & 2 & \cdots\\
\hline
\end{array}

整数 \( n \) を用いて、区間 \( [nb, (n+1)b – 1]\) に対応して \( 0 \leq a \bmod b \leq b – 1 \) となっていることが分かります。ここで、\( N \) 以下を満たす区間の数 \( m \) は、

\[m= \dfrac{N+1}{b} \]

となります。ある区間に \( K \leq a \bmod b \) となる \( a \) の数は、\( b – K \) となるので、全体で \( m(b – K) \) となります。次に、\( m + 1 \) 個目の区間を考えます。この区間は、\( N \) 以下の値も含まれることがあるので、その分を考慮します。\( m + 1 \) 個目区間の最初の値は、\( mb \) となるので、

\[ \max(0, N – (mb + K) + 1)\]

が条件を満たす \( a \) の個数となります。

コード