C++で「スーパー回文」（回文の2乗が回文になる数）を数える方法

本記事では、回文の2乗が回文となる数（スーパー回文）の個数を求めるC++プログラムについて詳しく解説します。

スーパー回文とは？

まず、2つの整数 L と R が与えられます。私たちのタスクは、この範囲 [L, R] 内に存在するスーパー回文の個数を求めることです。

スーパー回文とは、その数自身が回文であり、さらにその2乗も回文となっている特別な数のことです。例えば、「3」は回文であり、その2乗「9」も回文なので、3はスーパー回文です。

アルゴリズムの考え方

範囲内のすべての数を1つずつ調べるのは非効率です。そこで、次のようなアプローチを取ります。

• 回文を生成してから判定することで、探索範囲を大幅に絞り込む
• 桁数が奇数の回文と偶数の回文をそれぞれ生成する
• 生成した回文の2乗を計算し、それが範囲内かつ回文であればカウントする

C++での実装例

#include <bits/stdc++.h>
using namespace std;

// 数値が回文かどうかを判定する関数
bool if_palin(int x){
    int ans = 0;
    int temp = x;
    while (temp > 0){
        ans = 10 * ans + temp % 10; // 桁を反転させて構築
        temp = temp / 10;
    }
    return ans == x;
}

// スーパー回文の個数を返す関数
int is_spalin(int L, int R){
    // 回文生成の上限
    int LIMIT = 100000;
    int ans = 0;

    // 奇数桁の回文を生成してチェック
    for (int i = 0 ;i < LIMIT; i++){
        string s = to_string(i);
        string rs = s.substr(0, s.size() - 1); // 最後の1文字を除いて反転
        reverse(rs.begin(), rs.end());
        string p = s + rs;
        int p_sq = pow(stoi(p), 2);
        if (p_sq > R)
            break;
        if (p_sq >= L and if_palin(p_sq))
            ans = ans + 1;
    }

    // 偶数桁の回文を生成してチェック
    for (int i = 0 ;i < LIMIT; i++){
        string s = to_string(i);
        string rs = s; // 全体を反転
        reverse(rs.begin(), rs.end());
        string p = s + rs;
        int p_sq = pow(stoi(p), 2);
        if (p_sq > R)
            break;
        if (p_sq >= L and if_palin(p_sq))
            ans = ans + 1;
    }
    return ans;
}

int main(){
    string L = "4";
    string R = "1000";
    printf("%d\n", is_spalin(stoi(L), stoi(R)));
    return 0;
}

実行結果

4

コードの解説

if_palin 関数

この関数は、数値の桁を逆順に並べ替えた値が元の値と一致するかどうかで、回文かどうかを判定します。剰余演算と整数除算を組み合わせることで、文字列変換なしに効率的に反転処理を行っています。

is_spalin 関数

この関数が本アルゴリズムの核心部分です。全数を総当たりする代わりに、回文を直接構築します。

• 奇数桁の回文：数値の末尾1文字を除いた部分を反転して連結します（例：123 → 12321）
• 偶数桁の回文：数値全体を反転して連結します（例：123 → 123321）

生成した回文の2乗が範囲 R を超えた時点でループを抜けるため、無駄な計算を省けます。また、2乗が範囲 [L, R] 内にあり、かつ if_palin 関数で回文と判定されれば、カウンタを増やします。

計算量のメリット

単純な全探索では O(R) の計算量が必要ですが、この方法では回文を生成するため、実際に調べる候補数はぐっと少なくなります。特に大きな範囲を扱う場合に、この手法の優位性が際立ちます。

まとめ

このように、回文を事前に生成してから条件判定を行うアプローチにより、スーパー回文の個数を効率的に求めることができます。L = 4、R = 1000 の場合、出力は 4 となります（該当するのは 2、3、11、22 の4つです）。