C++で三乗の和がN（a³+b³=N）となるペア(a, b)の個数を数える

問題の概要

整数Nが与えられたとき、三乗の和がNに等しくなるような正数の順序付きペア(a, b)をすべて見つけ、その個数を求めるのが目標です。

これは、方程式 a³ + b³ = N の解を探索することで実現できます。aはNの立方根以下の範囲で調べ、対応するbは (N − a³) の立方根として計算できます。

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

入力 

N=35

出力 

a^3+b^3=Nとなるペア(a,b)の個数: 2

説明 

ペアは(2,3)と(3,2)。2^3+3^3=8+27=35

入力 

N=100

出力 

a^3+b^3=Nとなるペア(a,b)の個数: 0

説明 

条件を満たすペアは存在しません。

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

• 整数Nを受け取ります。

• 関数cubeSum(int n)はnを受け取り、三乗の和がnになる順序付きペアの個数を返します。

• ペアを数えるための変数countを0で初期化します。

• forループを使ってaを探索します。

• a=1から、nの立方根であるcbrt(n)未満の範囲まで繰り返します。

• bの三乗bcubeを「n − pow(a,3)」として計算します。

• bをcbrt(bcube)、つまりbcubeの立方根として求めます。

• pow(b,3)==bcubeが成立した場合、countを1増やします。

• すべてのループが終了した時点で、countには条件を満たすペアの総数が格納されています。

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

サンプルコード

#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int cubeSum(int n){
   int count = 0;
   for (int a = 1; a < cbrt(n); a++){
      int bcube=n - (pow(a,3));
      int b = cbrt(bcube);
      if(pow(b,3)==bcube)
         { count++; }
   }
   return count;
}
int main(){
   int N = 35;
   cout <<"Count of pairs of (a,b) where a^3+b^3=N: "<<cubeSum(N);
   return 0;
}

出力

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

Count of pairs of (a,b) where a^3+b^3=N: 2