この問題では最小公倍数 (LCM) を用いた周期性の解析を学習します。定期的なジョブやイベントの重なりを予測し、リソースの競合を防いだり、相乗効果を狙ったりするスケジューリングに役立ちます。
最小公倍数の求め方
2つの数 $A, B$ が同時に割り切れる最小の数が最小公倍数です。素因数分解を利用して計算します。
1. 素因数分解
- $28 = 4 \times 7 = 2^2 \times 7^1$
- $42 = 6 \times 7 = 2^1 \times 3^1 \times 7^1$
2. 各素因数の最大指数をとる
LCMを構成するには、各素因数について指数が大きい方を採用します：
- $2$ について: $2^2$ （28の方）
- $3$ について: $3^1$ （42の方）
- $7$ について: $7^1$ （両方共通）
$\text{LCM}(28, 42) = 2^2 \times 3^1 \times 7^1$
3. 計算の実行
$4 \times 3 \times 7 = 12 \times 7 = 84$
したがって、84日ごとに両方のイベントが重なります。
周期性の管理
LCMの概念はシステム運用で頻出です：
- Cronジョブ: 異なる間隔で走るバッチ処理が重なるタイミングの特定
- 信号機: 複数の信号が同時に青になるサイクルの計算
- 暗号理論: RSA暗号などでの周期性の利用