ABC290 D問題 Marking

手順 i だけ考える

手順 i だけを考えると、手順を $k$ 回繰り返したときの変数 $x$ の値は、 $k D \mod N$ になります。

変数 $x$ の値にダブりがでるまでの手順 i の繰り返し回数を考えてみます。

$D$ と $N$ の最大公約数を $g$ として、 $D = d g, N = n g$ と表します。( $d, n$ は互いに素)
$k D \mod N$ は $g$ の倍数になります。　0 から $N-1$ までの $N$ 個の数のうち、 $g$ の倍数は
$N/g = n$ 個です。
一方、 $k D \equiv 0 \pmod N$ となる、つまり $k D$ が $N$ の倍数となるためには、 $k$ が $n$ の倍数であることが必要です。
$k= 0,1,2,\cdots,n-1$ について、 $k D \mod N$ の値がダブらずに $n$ 個の $g$ の倍数にばらまかれて、
$k= n$ のときに $k=0$ と同じ $x = 0$ に戻ります。
そこで初めて、手順 ii が実行されます。

手順 ii の実行回数

$k= n$ のときに手順 ii が実行され、 $x=1$ になります。
そこから、 $k= n,n+1,n+2,\cdots,2n-1$ での $x$ の値は $k=0,\cdots,n-1$ のときの値に +1 したものになります。
そして、 $k= 2n$ のときに $k=n$ と同じ $x = 1$ に戻り、手順 ii によって $x = 2$ になります。
このように、手順 ii は $n$ ごとに実行されます。

知りたいのは $K-1$ 番目の $x$ の値です。 $K-1$ を $n$ で割ったときの商を $P$ 余りを $R$ とすると、
手順 ii は $P$ 回行われているため
$P + R D \mod N$
が求める答えになります。

コード例 (Julia)

function solve_test()

  # 入力
  readInts() =  parse.(Int,split(readline()))

  # 入力データ
  N,D,K = readInts()

  # 最大公約数
  g = gcd(N,D)

  # 周期 (何回で最初の位置に戻るか)
  n = div(N,g)

  # 手順 2-1 で加算する数の合計
  P = div(K,n)

  # 余り
  R = K % n

  ans = (P + R * D) % N

  println(ans)

end

function solve()

  # 入力
  readInt()  =  parse(Int,readline())

  # 入力データ
  T = readInt()

  for i = 1:T
    solve_test()
  end

end  # function solve

# main
solve()