クライアントからの着信時に処理すべき注文数をカウントするC++プログラム

3つの整数 n、m、z があるとします。あるオフィスでは、n 分ごとにクライアントから電話がかかってきて、m 分ごとに新しい注文（配達）が届きます。オフィスは合計 z 分間営業しています。

ここで求めたいのは、クライアントからの電話がかかった時点で未処理の注文が残らないようにするために、最低限いくつの注文を処理する必要があるかという数です。なお、注文を受け取る作業も、クライアントとの通話も、それぞれちょうど1分かかるものとします。

例えば、入力が n = 1、m = 2、z = 5 の場合、出力は 2 になります。これは、2分目と4分目に届いた注文を処理すればよいからです。

解法の考え方

この問題を解く鍵となるのは最小公倍数（LCM）です。クライアントからの電話と注文の到着が同時に重なるのは、n と m の両方の倍数である時刻、つまり lcm(n, m) 分ごとに発生します。

したがって、営業時間 z 分の中で注文を処理すべき回数は、次の式で求められます。

return z / ((n * m) / (nとmの最大公約数));

ここで (n * m) / gcd(n, m) は n と m の最小公倍数を表しています。最大公約数（gcd）を使うことで、オーバーフローを避けながら効率的に LCM を計算できます。

実装例

理解を深めるために、以下のC++による実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int solve(int n, int m, int z){
    return z / ((n * m) / __gcd(n, m));
}
int main(){
    int n = 1;
    int m = 2;
    int z = 5;
    cout << solve(n, m, z) << endl;
}

入力

1, 2, 5

出力

2

このように、最大公約数を利用した最小公倍数の計算により、営業時間内に処理が必要な注文の最小数を O(log(min(n, m))) の計算量で効率的に求めることができます。