CS Academy Round #21 - 0-K Multiple

• 問題
• AC

まずは全探索を考えることにする。例えば$K=7$のとき、$7 \rightarrow 70 \rightarrow 77 \rightarrow 700 \rightarrow 707 \rightarrow ...$のように昇順に$N$の倍数かどうかチェックしたい。これはキューを使えば簡単に実現できる。整数$i$をキューから取り出したら、$10i$と$10i+K$をキューに加えればよい。しかし、問題点が２つある:

1. そもそも全探索は間に合わない
2. 64ビット整数の範囲を容易に超えてしまう

１つ目の問題は、$N$を法として合同な整数を２度は処理しないことで解決する。$i \equiv j$なら$10i \equiv 10j$、$10i+K \equiv 10j+K$だから、代表元として最小のものだけ処理していけばよい。２つ目の問題は、キューに加える整数を$\mod N$を取った整数とすれば解決できそうだが、そうすると元の整数がわからなくなってしまう。この制約では２進法で$1 \rightarrow 10 \rightarrow 11 \rightarrow 100 \rightarrow 101 \rightarrow ...$のようにコーディングすれば64ビットに収まるので、これとペアでキューに加えれば良いようだ。しかし、上限の評価はそんなに明らかでもない。¹ 単方向リストで永続スタックを作る感じにしたほうが確実だと思った。

---

1. 解説にある通り、高々$N$ビットで十分なのはすぐにわかるが…… ↩︎