C++でnに最も近いmの倍数を求めるアルゴリズムと実装方法

問題の概要

2つの整数 n と m が与えられたとき、「n に最も近く、かつ m で割り切れる数」を見つけることを考えます。候補が複数存在する場合は、絶対値が最大となる数を返します。また、n が m で完全に割り切れる場合は、そのまま n を返します。

例えば、n = 13、m = 4 の場合、出力は 12 になります。13 に近い 4 の倍数としては 12 と 16 が候補ですが、13 との距離が近いのは 12 であるため、これが答えとなります。

解決の手順

この問題は、次のステップに従って解くことができます。

• まず q := n / m とし、n1 := m * q を計算します
• n * m > 0 の場合は n2 := m * (q + 1)、そうでない場合は n2 := m * (q - 1) とします
• |n - n1| < |n - n2| であれば n1 を返し、そうでなければ n2 を返します

C++による実装例

#include<iostream>
#include<cmath>
using namespace std;
int findClosest(int n, int m) {
    int q = n / m;
    int n1 = m * q;
    int n2 = (n * m) > 0 ? (m * (q + 1)) : (m * (q - 1));
    if (abs(n - n1) < abs(n - n2))
        return n1;
    return n2;
}
int main() {
    int n = 13, m = 4;
    cout << "Closest for n = " << n << ", and m = " << m << ": " << findClosest(n, m) << endl;
    n = 0; m = 8;
    cout << "Closest for n = " << n << ", and m = " << m << ": " << findClosest(n, m) << endl;
    n = 18; m = -7;
    cout << "Closest for n = " << n << ", and m = " << m << ": " << findClosest(n, m) << endl;
}

実行結果

Closest for n = 13, and m = 4: 12
Closest for n = 0, and m = 8: 0
Closest for n = 18, and m = -7: 21

アルゴリズムのポイント

このアルゴリズムの鍵となるのは、C++ の整数除算が「0 の方向へ丸める」という仕様である点です。q = n / m を計算することで、n に最も近い候補のひとつである n1 = m * q が得られます。続いて、n と m の積が正か負かを判定することで、もうひとつの候補 n2 が n1 のどちら側に位置するかを決定し、両者の絶対距離を比較することで最終的な答えを確定します。

3つのテストケースの結果を見てみましょう。n = 13、m = 4 の場合は 12、n = 0、m = 8 の場合は n 自体が m で割り切れるため 0、n = 18、m = -7 の場合は 21(= -3 × 7)が返されます。負の除数を含むケースでも正しく動作することが確認できます。

この手法は剰余演算やループを一切使わず、定数時間 O(1) で答えを求められる点が大きな特徴です。大きな数値に対しても高速に動作するため、競技プログラミングや実務の両方で役立つテクニックと言えます。