Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 290 D問題 Marking

AtCoder ABC290 ABC 400 pts D問題

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

マス $0,1,2, \dots, (N-1)$ と名付けられた $N$ 個のマス目に次のようにして印を付けていく.

最初, マス $0$ に印を付ける.
以下の手順を回繰り返す.
- 直前に印を付けたのがマス $A$ であるとしたとき, $x \gets (A+D) \bmod{N}$ とする.
- マス $x$ に印がついている限り, $x \gets (x+1) \bmod{N}$ とする.
- マス $x$ に印を付ける.

$T$ 個のテストケースについて答えよ.

制約

$1 \leq T \leq 2 \times 10^5$
$1 \leq K \leq N \leq 10^9$
$1 \leq D \leq 10^9$

解法

この説明では非負整数 $k$ と $0$ 以上 $N$ 未満の整数 $n$ に対して, マス $n$ とマス $(n+kN)$ を同一視することにする.

このとき, $g=\gcd(N,D), N':=N/g$ とすると, 印の付け方は次のように上から実行される.

$0 \to D \to 2D \to \dots \to (N'-1)D$
$1 \to D+1 \to 2D+1 \to \dots \to (N'-1)D+1$
$\vdots$
$(g-1) \to D+(g-1) \to 2D+(g-1) \ to \dots (N'-1)D+(g-1)$

ここで, 上から $(r+1)$ 段目にある $kD+r$ という整数は $g$ で割ると $r$ 余る $0$ 以上 $N$ 以下の整数全てである.

このことを頭に入れておくと, $N'$ 回の印付けで余りが $1$ 増えるだけで後は繰り返しであるというふうに見ることができ, 求めるべき答えとして以下のように立式できる.

$\left \lfloor \dfrac{(K-1)}{N'} \right \rfloor+( (K-1) \bmod{N'} \times D) \bmod{N}$

ここで, $(K-1)$ を $N'$ で割った商と余りを $Q,R$ とすると,

$RD=( (K-1)-N'Q)D=(K-1)D-N'DQ$

となるが, $g=\gcd(N,D)$ であるから, $N'DQ=N (D/g) Q$ であるから,

$( (K-1) \bmod{N'} \times D) \bmod{N}=(K-1)D \bmod{N}$

よって, 最終解答として

$\left \lfloor \dfrac{g(K-1)}{N} \right \rfloor+( (K-1)\times D) \bmod{N}$

を得る.

1テストケース当たり $O(\log (N+D))$ 時間で計算できるので, 全体でも $O(T \log \max (N+D))$ 時間で計算でき, 十分高速である.