C++で総和が完全平方数となる配列内のペアの個数を求める方法

N個の要素からなる配列が与えられたとき、i ≠ j を満たすペア (Arr[i], Arr[j]) のうち、Arr[i] + Arr[j] の和が完全平方数（perfect square）となるものの個数を求めるのが本記事の目的です。

この問題は、各ペアの和を計算し、その平方根が整数（床関数の値）と一致するかどうかを判定することで解けます。具体的には、sqrt(Arr[i]+Arr[j]) − floor(sqrt(Arr[i]+Arr[j])) == 0 が成り立てば、その和は完全平方数であると分かります。

具体例で確認してみましょう。

例1

入力：Arr[] = { 4, 3, 2, 1, 2, 4 }、N = 6
出力：和が完全平方数となるペアの個数 → 2

Arr[1]+Arr[3] = 4、sqrt(4)−floor(4) = 0 → 4 は完全平方数
Arr[2]+Arr[4] = 4、sqrt(4)−floor(4) = 0 → 4 は完全平方数
残りのペアの和は 7, 6, 5, 8 となり、いずれも完全平方数ではありません。

例2

入力：Arr[] = { 3, 3, 3, 3, 3 }、N = 5
出力：和が完全平方数となるペアの個数 → 0

説明：すべてのペアの和が 6 となり、6 は完全平方数ではないため該当するペアは存在しません。

プログラムで使用するアプローチ

• ランダムな整数で初期化された整数型配列 Arr[] を用意します。
• 配列 Arr[] の長さを格納する変数 n を宣言します。
• 関数 countPairs(int arr[], int n) は、配列とその長さを引数として受け取り、和が完全平方数となるペアの個数を返します。
• ペアを構成する各要素について、二重の for ループを使って配列を走査します。
• 外側のループは 0 ≤ i < n−1、内側のループは i < j < n の範囲で繰り返します。
• arr[i] と arr[j] の和を計算します。
• sqrt(sum) として和の平方根を求めます。
• sqr − floor(sqr) == 0 が成り立つかを判定します。成り立っていれば和は完全平方数であるため、count をインクリメントします。
• すべてのループが終了した時点で、count には和が完全平方数となるペアの総数が格納されています。
• 結果として count を返します。

C++実装例

#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int countPairs(int arr[], int n){
    int count=0;
    int sum=0;
    double sqr=0;
    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++){
            sum=arr[i]+arr[j];
            sqr=sqrt(sum);
            if( sqr-floor(sqr)==0 ){
                count++;
                //cout<<endl<<"a :"<<arr[i]<<" b :"<<arr[j]; //表示用
            }
        }
    }
    return count;
}
int main(){
    int arr[] = { 1, 2, 4, 8, 5, 6 };
    // arr[] のサイズ
    int n = sizeof(arr) / sizeof(int);
    cout <<endl<<"Pairs whose sum is perfect square :"<<countPairs(arr, n);
    return 0;
}

実行結果

上記のコードを実行すると、次のような出力が得られます。

Pairs whose sum is perfect square :2

このように、平方根と floor 関数を組み合わせたシンプルな判定により、配列内のすべてのペアを効率的に調べて、和が完全平方数となる組み合わせの総数を求めることができます。