競プロがんばりたい

Remainder Reminder

精進

ARC091-D "Remainder Reminder"

あけましておめでとうございます．

提出コード

考察

下の図 $1$ のような表を自分は書きました．

これは入力が

$10 \ 3$

のときの表です．

見方としては， $a$ を決めたときに条件を満たす $b$ を右に書き並べていったものです．

なお，考察がしやすいよう $N=10$ より大きい $a$ も一部書いています．

( $b=0$ を書き込む欄がありますが， $0$ 割りに相当するのでありえないです．表を修正するのが面倒だったのです．)

f:id:chankilu23:20201231193358j:plain

$b$ を固定して考えてみます．(図では $b=4, 6$ を取り上げてみました．)

・ $b=4$ のとき

上から順に $a$ を $b=4$ で割った余りを見ていくと，

$1, 2, 3, 0, 1, 2, 3, 0, ...$

と循環しているのがわかります．(当然ですが)

循環している塊ごとに赤枠で分けました．

一つの塊内には当然 $4$ つの数字が存在します．

この赤枠内で条件を満たす $a$ の数は， $4-3=1$ 個です．

( $b=4$ 個中 $K=3$ 個が条件を満たさないので )

そして $N=10$ 以下で繰り返しの赤枠の総数は， $10/4 = 2$ 個です．

( $N=10$ 個の整数を $b=4$ 個の塊ごとに見ているので )

よって，繰り返し分の中で条件を満たす $a$ の個数は $1 \times 2 = 2$ 個です．

もう一歩考えることがあるのですが， $b=4$ では考えにくいので次にいきます．

・ $b=7$ のとき

上と同様に考えると，赤枠内で条件を満たす $a$ の数は $7-3 = 4$ 個．

繰り返しの赤枠の数は $10/7 = 1$ 個．

よって，繰り返し分の中で条件を満たす $a$ の個数は $4 \times 1 = 4$ 個です．

$b=4$ では飛ばしたものを考えます．

図を見ればわかりますが，繰り返しが終わった後の赤枠(途中で途切れている)内にも残っているのが確認できます．

赤枠の繰り返しが終わったとき，残りの $a$ の候補の数は $10 \% 7=3$ です．

このうち， $3-1=2$ 個は条件を満たさないので，候補の数から引くことで， $3-2=1$ を得ます．

よって赤枠の繰り返し分と合わせて， $b=7$ のときの条件を満たす $a$ の数は $4+1=5$ です．

一般化します．

$b$ を固定したとき，赤枠の繰り返し数は， $N/b$ です．

その各々に対して，赤枠内の条件を満たす $a$ の数は $b-K$ 個です．

よって，繰り返し分の赤枠で考えると， $N/b \times (b-K)$ 個だけあります．

ただし， $b-K \lt 0$ となることもあるので， $N/b \times$ max $(0, b-K )$ とします．

残りは繰り返しからはみ出たやつらです．

残りの $a$ の候補数は $N \% b$ です．

そのうち， $K-1$ 個が条件を満たさないので， $N \% b - (K-1)$ です．

ただし， $N \% b - (K-1) \lt 0$ となることもあるので，max $(0, N \% b - K + 1)$ とします．

これを $b+1$ から $N$ まで順に足していけば $O(N)$ で答えが出ます．

$K=0$ のときだけ上記の方法ではうまくいきません．

でも $K=0$ では全ての組み合わせで条件を満たすので， $N \times N$ を出力すればOKです．

感想

年内にACはしていましたが忙しくて記事にはできませんでした．

なかなか面白い問題でしたね．

良いところまでは気づいていましたが，最後の細かい詰めは知り合いに助けてもらいました．

整数の問題は好きなので得意になりたいです．