C++で平方数の和を判定するアルゴリズムを解説

問題の概要

負でない整数 c が与えられたとき、a² + b² = c を満たす2つの整数 a と b が存在するかどうかを判定する問題です。

例えば、入力が 61 の場合、61 = 5² + 6² と表せるため、出力は True になります。

解法のアプローチ

この問題は、0 から √c までの各整数 i について「c − i² が完全平方数であるか」を順に調べることで解けます。以下の手順に従います。

• 関数 isPerfect() を定義します。引数として x を受け取ります。
• sr := x の平方根 を計算します。
• (sr − sr の切り捨て値) が 0 であれば true を返します。これにより x が完全平方数かどうかを判定できます。
• メインの処理では以下を行います。
• c が 0 と等しい場合は true を返します。
• i を 0 で初期化し、i が √c の切り上げ値未満である間、i を1ずつ増やしながら以下を繰り返します。
  • b := c − i × i を計算します。
  • isPerfect(b) が true であれば、true を返します。
• ループが終了しても見つからなければ、false を返します。

実装例

理解を深めるために、以下の C++ 実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    bool isPerfect(int x){
        long double sr = sqrt(x);
        return ((sr - floor(sr)) == 0);
    }
    bool judgeSquareSum(int c) {
        if (c == 0)
            return true;
        int b;
        for (int i = 0; i < ceil(sqrt(c)); i++) {
            b = c - i * i;
            if (isPerfect(b))
                return true;
        }
        return false;
    }
};
main(){
    Solution ob;
    cout << (ob.judgeSquareSum(61));
}

入力

61

出力

1

計算量の評価

このアルゴリズムの時間計算量は O(√c) です。i を √c まで走査し、各ステップで平方根の判定を行うためです。空間計算量は O(1) で、追加のメモリはほとんど必要ありません。平方根の計算には浮動小数点数の誤差がつきものなので、サンプルコードのように long double を使うことで精度を高めています。

補足：二ポインタ法による別解

同様の問題は、左端を 0、右端を √c とした二ポインタ法でも解けます。a² + b² の値が c より小さければ左ポインタを、大きければ右ポインタを動かすことで、同じく O(√c) の計算量で判定できます。浮動小数点誤差を避けたい場合は、整数演算のみで完結するこの方法も有効です。