2数が同期する周期

[tipstar0125]

ABC209 D - Marking https://atcoder.jp/contests/abc290/tasks/abc290_d

[tipstar0125]

2つの数をそれぞれ足していって、最小で同じになる（同期する）数を考える。 ⇒最小公倍数

例えば、2つの数A, Bがあったとして、A=12, B=9のときの最小公倍数は36であり、実際に足していくと同期するタイミングと一致する。 Bに関してmod Aをとると、最小公倍数の倍数が周期/B個現れ、2周期以降は同じ数列が繰り返される。 A: 0, 12, 24, 36 B: 0, 9, 18, 27, 36 (B mod A: 0, 9, 6, 3, 0)

[tipstar0125]

2つの変数N, Dで考える。

• 周期以上のKであれば、それ以降は同じ数列が繰り返されることを利用して、1周回におけるどの最小公倍数の倍数になるかを計算
  • (K-1) x D mod N
• 何周回目か（シフト数）を計算
  • 周期 T = lcm(N, D)
  • 1周回の数 n = T / D
  • シフト数 = (K - 1) / n

[tipstar0125]

lcm(N, D)/Dステップで0に帰ってくる