CODE THANKS FESTIVAL 2017(Parallel) D – Bus Tour

Bus Tour

https://atcoder.jp/contests/code-thanks-festival-2017-open/tasks/code_thanks_festival_2017_d

方針

答えの候補を \( a \) とすると、\( 0 \leq a \leq M – 1 \) であることが分かります。

バスの台数を \( x \)、グループ数を \( y \) とすると、

\[ 0 \leq Mx – Ny \leq M – 1\]

を満たします。\( g = gcd(N, M)\) とし、\( N = gn \)、\(M = gm\) とすると、

\[ 0 \leq g(mx – ny) \leq gm – 1\]

\[ 0 \leq mx – ny \leq m – \dfrac{1}{g} \]

と計算できます。\( mx – ny  \) は整数であることから、

\[ 0 \leq mx – ny \leq m – 1 \]

となるので、

\[ 0 \leq Mx – Ny \leq M – g \]

となります。

コード

シェアする

  • このエントリーをはてなブックマークに追加

フォローする