C++で最も近い約数のペアを効率的に求めるアルゴリズム

問題概要

整数 num が与えられたとき、積が num + 1 または num + 2 と等しくなるような2つの整数のうち、絶対差（2つの値の差の絶対値）が最小になるペアを求めます。返す順序は問われません。

例えば、入力が 8 の場合を考えてみましょう。
num + 1 = 9 のとき、最も近い約数のペアは [3, 3] です。
num + 2 = 10 のとき、最も近い約数のペアは [2, 5] です。
両者を比較すると、差がより小さいのは [3, 3] なので、これが出力となります。

解法のアプローチ

この問題は「約数列挙」と「差の比較」を組み合わせることで解けます。手順は以下の通りです。

• getDiv() というメソッドを定義します。引数として整数 x を受け取ります。
• diff を無限大（INT_MAX）で初期化し、サイズ2の配列 ret を作成します。
• i = 1 から始めて i * i <= x の間、i を1ずつ増やしながらループします。
  • x が i で割り切れる場合：
    • a = i、b = x / i とする
    • newDiff = |a - b| を計算する
    • newDiff < diff であれば、diff = newDiff とし、ret[0] = a、ret[1] = b を更新する
• ret を返します。
• メイン処理では op1 = getDiv(num + 1) と op2 = getDiv(num + 2) をそれぞれ求めます。
• |op1[0] - op1[1]| <= |op2[0] - op2[1]| であれば op1 を、そうでなければ op2 を返します。

計算量について

この手法では、平方根までの数だけを試すため、各 getDiv() の呼び出しは O(√x) 時間で完了します。全体としても非常に効率的であり、大きな num に対しても高速に動作します。

C++による実装例

以下の実装を見ると、理解がより深まるでしょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   vector <int> getDiv(int x){
      int diff = INT_MAX;
      vector <int> ret(2);
      for(int i = 1; i * i <= x; i++){
         if(x % i == 0){
            int a = i;
            int b = x / i;
            int newDiff = abs(a - b);
            if(newDiff < diff){
               diff = newDiff;
               ret[0] = a;
               ret[1] = b;
            }
         }
      }
      return ret;
   }
   vector<int> closestDivisors(int num) {
      vector <int> op1 = getDiv(num + 1);
      vector <int> op2 = getDiv(num + 2);
      return abs(op1[0] - op1[1]) <= abs(op2[0] - op2[1]) ? op1 : op2;
   }
};
main(){
   Solution ob;
   print_vector(ob.closestDivisors(8));
}

入力

8

出力

[3,3]

まとめ

この問題のポイントは、num + 1 と num + 2 のどちらか一方は必ず偶数になるため、必ず有効な約数のペアが存在することです。約数を効率的に列挙し、差が最小のペアを選ぶことで、シンプルかつ高速に解答できます。