[AtCoder] CODE THANKS FESTIVAL 2017(Parallel) D – Bus Tour

問題

方針

答えの候補を \( 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 \]
となるので、\( g \) を掛けると、
\[ 0 \leq Mx – Ny \leq M – g \]
となります。

コード

提出したコード

最大公約数