C++で解く最大の回文積（パリンドローム積）問題

問題の概要

整数 n が与えられたとき、「2つの n 桁の数をかけ合わせて作ることができる最大の回文数」を求める問題を考えます。積は非常に大きな値になるため、結果は 1337 で剰余（mod）を取って返します。

例えば入力が 2 の場合、答えは 987 となります。これは次のような計算によるものです。
987 = (99 × 91) mod 1337 = 9009 mod 1337 = 987

解法のアプローチ

回文数は「前半の数字列を逆順に並べたものを後半に付け足す」ことで生成できます。そこで、前半部分となる候補 h を大きい方から順に試し、そこから回文を作り、その回文が2つの n 桁の数の積になっているかを確認していきます。具体的な手順は以下の通りです。

• maxVal を 10^n − 1（n 桁の最大値）とする
• minVal を maxVal / 10 とする
• h を maxVal から開始し、h > minVal である間、1 ずつ減らしながら以下を繰り返す
  • left := h、right := 0 と初期化する
  • i を h から始め、i > 0 である間、「right = right * 10 + i mod 10」「left *= 10」「i /= 10」を繰り返して h の桁を反転させる
  • x := left + right とすることで、h を前半とする回文 x が得られる
  • i を maxVal から minVal より大きい間、1 ずつ減らしながら以下を確認する
    • i < x / i となった場合（i が √x を下回った場合）、大きい側の候補はすべて調べ済みのため、これ以上探索しても有効な因数の組は見つからず、ループを抜けてよい
    • x mod i == 0 となった場合、x は2つの n 桁の数の積であるため、x mod 1337 を返す
• 最後まで見つからない場合は 9 を返す

全ての積を総当たりで調べるのではなく、回文を大きい順に生成して因数の存在だけを確認するため、効率よく答えにたどり着けるのがポイントです。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
    int largestPalindrome(int n) {
        int maxVal = pow(10, n) - 1;
        int minVal = maxVal / 10;
        for(int h = maxVal; h > minVal; h--){
            lli left = h;
            lli right = 0;
            for(lli i = h; i > 0; right = right * 10 + i % 10, left*= 10, i/= 10);
            lli x = left + right;
            for(int i = maxVal; i > minVal; i--){
                if(i < x / i) break;
                if(x % i == 0) return x % 1337;
            }
        }
        return 9;
    }
};
main(){
    Solution ob;
    cout << (ob.largestPalindrome(3));
}

入力

3

出力

123

この例では n = 3 を与えています。2つの3桁の数の積で作れる最大の回文は 906609（= 913 × 993）であり、906609 mod 1337 = 123 となるため、出力は 123 になります。

計算量のポイント

前半候補 h の走査には最大 O(10^n)、内側の因数探索にも O(10^n) かかるように見えますが、break 条件によって探索範囲が √x までに抑えられるため、単純な総当たりと比べて大幅に高速に動作します。