CODE THANKS FESTIVAL 2017: D - Bus Tour

問題

D - Bus Tour

解説

空席の最大数を見つけるという問題であることから、バスとグループを必要分だけ互いに増やし続けていくと、空席数に周期が生じることが思いつく。

どのようなパターンだと空席数が多くなるだろうか。とが互いに素であれば、1ずつ空席数を変化させられるため、最大の空席数がとなる。

こういったことにヒントを得ると、バスとグループを1周期分になるまで増やし続けたとき、最終的に空席数をどの単位で変化させられたかを考えれば良さそうである。

よって、空席数はの単位で変化させることができて、空席の最大数はではないかという予想が立ち、実際これが解である。

証明はEditorialを参照した。

乗車するグループの数をとすると乗車人数の和, 空席を持つバスの乗車人数に対して、 であり、の最小化をすれば良いが、を固定すると、についての一次合同式になる。ゆえにが解を持つ条件はがの倍数のときである。

一次合同式について

int main() {
  unsigned N, M; cin >> N >> M;
  cout << M - __gcd(N, M) << endl;
}