問題
解説
空席の最大数を見つけるという問題であることから、バスとグループを必要分だけ互いに増やし続けていくと、空席数に周期が生じることが思いつく。
どのようなパターンだと空席数が多くなるだろうか。と
が互いに素であれば、1ずつ空席数を変化させられるため、最大の空席数が
となる。
こういったことにヒントを得ると、バスとグループを1周期分になるまで増やし続けたとき、最終的に空席数をどの単位で変化させられたかを考えれば良さそうである。
よって、空席数はの単位で変化させることができて、空席の最大数は
ではないかという予想が立ち、実際これが解である。
証明はEditorialを参照した。
乗車するグループの数をとすると乗車人数の和
, 空席を持つバスの乗車人数
に対して、
であり、
の最小化をすれば良いが、
を固定すると、
についての一次合同式になる。ゆえに
が解を持つ条件は
が
の倍数のときである。
int main() { unsigned N, M; cin >> N >> M; cout << M - __gcd(N, M) << endl; }