[AtCoder] CODE THANKS FESTIVAL 2017(Parallel) D – Bus Tour
問題
https://atcoder.jp/contests/code-thanks-festival-2017-open/t...方針
答えの候補を \( 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 \]
となります。
コード
提出したコード
https://atcoder.jp/contests/code-thanks-festival-2017-open/s...最大公約数
typedef long long ll;
ll gcd(ll m, ll n) {
if (n == 0) return m;
else return gcd(n, m % n);
}