CODE THANKS FESTIVAL 2017(Parallel)-D：Bus Tour(300)

数学

問題

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

1グループN人のグループに対して、定員M人のバスを用意する。すべての参加者がバスに乗り込めるような最小台数用意するとき、バスの最大の空席数を求めよ。ただしグループ数は任意である。

  • 制約 1 <= n <= 109 1 <= m <= 109 n,mは整数

グループ数を a 、バスの台数を b とするとバスの空席数は 0 <= M*b - N*a <= M-1 で与えられる。 M*b - N*a を最大化したい。

考えた解法

M*b - N*a = k とすると、これが解をもつとき gcd(M, -N) = g として k = g*l (lは任意の自然数) と表すことができる。
kを最大化するとき g*l が M-1 以下の範囲で取りうる最大値を求めることになる。

0 <= g*l <= M-1 であったから、
0 <= l <= (M-1)/g と l は整数であることから
l = floor((M-1)/g) である。

よって、k = g*floor((M-1)/g) g = gcd(M, -N) が求める解である。

公式解答

考え方については似ているように思えるが、重要な考察を含んでいるので自分なりにまとめてみる。

0 <= M*b - N*a <= M-1 を満たすということは、M*b - N*a は M で割った余りと一致する。よってMで法をとり、-N*a modM である。
うまく余りをとることで、考察がすすむ問題も多い。
-N*a modM ⇔ M - (N*a modM) である。N*a ≡ k modM となる最小の自然数 k を求めたい。
aを変数とした一次合同式 N*a ≡ k modM について、a が解をもつ条件は k が gcd(M, N) の倍数であるときである。よって最小の k は k = gcd(M, N) である。
したがって求める解は M - gcd(M, N) である。