C++でa²+b²=c²かつ1≦a≦b≦c≦nを満たすトリプレット（a、b、c）の個数を数える方法

問題概要

整数 n が与えられます。この課題の目的は、以下の2つの条件を満たすトリプレット（3つの数の組み合わせ）を見つけ出し、その個数を求めることです。

• a² + b² = c²

• 1 ≦ a ≦ b ≦ c ≦ n

この問題は、1 ≦ a ≦ n および 1 ≦ b ≦ n の範囲で二重ループを実行することで解くことができます。各ループ内で c を計算し（c = sqrt(a² + b²)）、両方の条件を満たす場合にカウントを増やしていきます。

具体例を使って理解しましょう。

入力 ： N = 5

出力 ： トリプレットの個数 ： 1

説明 ：

a=3、b=4、c=5 のとき、両方の条件が満たされます。

入力 ： N = 3

出力 ： トリプレットの個数 ： 0

説明 ：

条件1と条件2の両方を満たすトリプレットは存在しません。

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

• 整数 N に、探索対象となる範囲 [1, N] の上限値を格納します。

• 関数 countTriplets(int n) は n を引数として受け取り、a²+b²=c² かつ 1 ≦ a ≦ b ≦ c ≦ n を満たすトリプレットの個数を返します。

• 変数 count は該当するトリプレットの個数を格納し、初期値は 0 です。

• 変数 sum には a と b の二乗の和を格納します。

• a = 1 から n まで、また b = a から n までループしながら、sum = a*a + b*b を計算し、その平方根を c（sqrt(sum)）とします。

• 計算した c が c*c == sum を満たし、かつ b ≦ c && c ≦ n である場合（条件1と条件2の両方が成立する場合）に処理を進めます。

• 現在の a、b、c が両方の条件を満たしているため、count をインクリメントします。

• a = n、b = n に達するまでこの処理を繰り返します。最終的に count には条件を満たすトリプレットの総数が格納されます。

• 求めた count を結果として返します。

実装例

#include <bits/stdc++.h>
using namespace std;
int countTriplets(int n){
    int count = 0;
    int a,b,c;
    a=b=c=1;
    int sum=0;
    for (a = 1; a <= n; a++) //1<=a<=n{
        for (b = a; b <= n; b++) //1<=a<=b<=n{
            sum = a*a + b*b; //a^2 + b^2 =c^2
            c = sqrt(sum);
            if (c * c == sum && b<=c && c<=n) //1<=a<=b<=c<=n のチェック{
                count++;
                cout<<endl<<"a :"<<a<<" b :"<<b<<" c :"<<c; //トリプレットの表示
            }
        }
    }
    return count;
}
int main(){
    int N = 15;
    cout <<endl<< "Number of triplets : "<<countTriplets(N);
    return 0;
}

出力結果

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

a :3 b :4 c :5
a :5 b :12 c :13
a :6 b :8 c :10
a :9 b :12 c :15
Number of triplets : 4

このように、N = 15 の場合は (3, 4, 5)、(5, 12, 13)、(6, 8, 10)、(9, 12, 15) の4つのトリプレットが条件を満たすことがわかります。計算量は O(n²) となるため、n が大きくなると処理時間が増加する点には注意が必要です。