ABC090 D - Remainder Reminder

ABC090 D - Remainder Reminder https://atcoder.jp/contests/abc090/tasks/arc091_b (opens in a new tab) (どうやら ARC でも出題があったらしい) 緑上位。

まともにやると $O(N^2)$ 系のアルゴリズムのため、 $a,b$ のいずれかを固定した上でもう片方に規則性を見出す問題となる。

$b$ の方を固定するとなんとなく規則性がありそうだが、結局分からずじまい。 少し具体的な例で考えてみよう。

今 $b=5$ を固定すると、各 $a$ に対して、 $0 \% 5=0$ $1 \% 5=1$ $2 \% 5=2$ $3 \% 5=3$ $4 \% 5=4$ $5 \% 5=0$ $6 \% 5=1$ $:$ と、 $0,1,2,3,...,b-2,b-1,0,1,2,3,...,b-2,b-1,0,1,2,...r$ (ただし $r<b$ ) と規則正しく並んでいくことが分かる。

繰り返しの回数と最後の余りの部分を機械的に処理できるかがポイントで、これは divmod(n, b) によって簡単に求めることが出来そうである。

繰り返しの部分の $k,k+1,...,b-2,b-1$ が条件を満たす $a$ であり、この数は max(0, b - k) により求まる。 最後の余りの部分では、 $k,k+1,...,r$ が条件を満たす $a$ であり、この数は max(0, r - k + 1) により求まる。

最も重要なポイントは $a=0$ を含めたことであろう。これによってかなり簡単に考えることが出来た。 最後に $a=0$ で条件を満たす場合( $k=0$ )