久々にABCの参加した割には、D問題を時間中に通せたのでウッキウキな気分で解説を書いてみます。初めての試みなのでわかりにくいかも…
問題はこちらからどうぞ。
愚直な解法は…
愚直な解法が許されるのであれば、問題文に記された処理を行うプログラムを作成すれば良いですが、$T= 10^5 ,K = 10^9$のときにTLEになります。そこで、計算量を抑える工夫が必要になります。愚直解法(シミュレーションの実装)を解答には採用できませんが、そこからヒントを得られることもあるので、実際にシミュレーションをして考察してみます。
簡単なシミュレーション
以下では、既に印がつけられているマスに到達することを「衝突」と呼ぶことにします。
例として$N = 15, D = 5$のときについて調べてみます。以下では$N=15$を法とする剰余計算であることに注意してください。
- $0$に印をつける
- $0 + 5 = 5$に印をつける
- $5 + 5 = 10$に印をつける
- $10 + 5 = 0$に印をつけたいが、衝突しているので$0+1 = 1$に印をつける
- $1 + 5 = 6$に印をつける
- $6 + 5 = 11$に印をつける
- $11 + 5 = 1$に印をつけたいが、衝突しているので$1 + 1 = 2$に印をつける
- $2 + 5 = 7$に印をつける
- $7 + 5 = 12$に印をつける
- $12 + 5 = 2$に印をつけたいが、衝突しているので$2 + 1 = 3$に印をつける
- $3 + 5 = 8$に印をつける
- $8 + 5 = 13$に印をつける
- $13 + 5 = 3$に印をつけたいが、衝突しているので$3 + 1 = 4$に印をつける
- $4 + 5 = 9$に印をつける
- $9 + 5 = 14$に印をつける
以上15回の操作で全てのマスに印がつけられました。
この例では3回おきに、既に印がつけられたマスに衝突することがわかります。このことから、一定の間隔で衝突が起こると予測できます。
予測の妥当性
前節のシミュレーションで一定の間隔で衝突が起こることが予測できました。この予測が正しいことを示します。
まず、$\overline{D} := D \mod N$とします。このとき、ある整数$k$を用いて、$D = kN + \overline{D}$と表せるので、$A + D \mod N = A + \overline{D} \mod N$になります。この事実を用いて、「$A$の初期値$A^{\mathrm{init}}$に対して$A^{\mathrm{init}}+n\overline{D} \mod N = A^{\mathrm{init}}$となるような$n$として考えられるものがなにか」を考えればよいです。
$N$の倍数かつ$\overline{D}$の倍数となる最小の数は$\mathrm{lcm}(N,\overline{D})$なので、最小の$n$として$n=\mathrm{lcm}(N, \overline{D})/\overline{D}$が考えられます。したがって、$\mathrm{lcm}(N, \overline{D})/\overline{D}$回の操作を行うと衝突が発生します。衝突後、$A^\mathrm{init}$をインクリメントして、$\mathrm{lcm}(N, \overline{D})/\overline{D}$回の操作を行うと再び衝突が発生します。以降同様の操作を繰り返します。そもそもとして、任意の$A$に対して$A + \left(\mathrm{lcm}(N, \overline{D})/\overline{D}\right)\overline{D} \mod N = A$が成り立ちます。以上により、$\mathrm{lcm}(N, \overline{D})/\overline{D}$回おきに衝突が発生することがわかり、前節での予測が正しいことが示されました。
解答
$A^{\mathrm{init}}$を「一回目に印をつける$0$、またはマスのインクリメント直後の$x$」としましょう。このとき、1回目、またはマスのインクリメントの直後から$\mathrm{lcm}(N,\overline{D})/\overline{D}$回の操作を行うと衝突が発生します。インクリメントを行う回数は、衝突回数と等しいので、$K = 1$でマス$0$に印をつけることに注意して、インクリメントを行う回数は$\lfloor (K-1) / (N / \mathrm{gcd}(N, \overline{D})) \rfloor$になります。$\mathrm{lcm}(N,\overline{D})=N\overline{D}/\mathrm{gcd}(N,\overline{D})$の関係式を用いました。そして、次に考えるべきは、すべてのインクリメントが行われた後、何回$\overline{D}$が加算されるかです。これは、$(K-1) \mod (N / \mathrm{gcd}(N, \overline{D}))$回です。したがって、求めるマスの番号は以下の式で求めることができます。
$$
\left\lfloor \frac{K-1}{N/ \gcd(N, \overline{D})} \right\rfloor + \left((K - 1) \mod (N/ \gcd(N, \overline{D}))\right)\overline{D}
$$
この式による計算結果は上記のシミュレーションの結果と確かに一致します。一連の処理の計算量は$\gcd$の計算量のオーダになるので、十分高速になりました。したがって、この計算を行うプログラムがACとなります。