平方三角形數（立方和）

---

平方三角形數，也稱為三角平方數，是一個既是三角形數又是完全平方數的數。

平方三角形數有無限多個可能的值；前幾個是：

0, 1, 36, 1225, 41616...

三角形數或三角數是計數按等邊三角形排列的物體。第n個三角形數是具有n個點的三角形排列中的點數，等於從1到n的n個自然數之和。從第0個三角形數開始的三角形數序列是：

0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55...

完全平方數或平方數是某個整數與其自身的乘積。完全平方數的序列是：

0, 1, 4, 9, 16, 25, 36, 49...

問題陳述

給定一個數字Sum。如果Sum等於前n個自然數的立方和，則列印n；否則，列印-1。

示例1

輸入

36

輸出

3

解釋 − Sum是前3個自然數的立方和。

1*1*1 + 2*2*2 + 3*3*3 = 36

示例2

輸入

22

輸出

-1

解釋

1*1*1 + 2*2*2 = 9，而 1*1*1 + 2*2*2 + 3*3*3 = 36，因此，不存在立方和等於Sum的自然數。

我們有兩種解決這個問題的方法。

方法1

暴力方法是計算整數的立方並存儲它們的和。當和等於或小於給定的Sum時，我們將這樣做。然後，如果和等於給定的數字，則列印n，否則列印-1。

虛擬碼

Start
temp = 0 
i = 0
While temp <= Sum:
	i = i + 1
	add cube of i to temp
if temp is equal to Sum
	then print n
else
	print -1
End

示例

下面是一個C++程式，用於檢查給定數字是否等於前n個自然數的立方和。

#include <iostream>
using namespace std;
// This function returns n if the sum of cubes of first
// n natural numbers is equal to the given Sum
int calcSquaredTriangularNumber(int Sum){
   // initialize a temporary variable to store sum
   int temp = 0;
   // Adding cubes of the numbers starting from 1
   int n = 0;
   while ( temp < Sum){
      n++;
      temp += n * n * n; 
   }
   // If temp becomes equal to sum return n
   if (temp == Sum){
      return n;
   }
      // otherwise return -1
   return -1;
}

int main(){
   int Sum = 36;
   // Function call
   int n = calcSquaredTriangularNumber(Sum);
   if(n>0){
      cout << n ;
      return n;
   }
   else{
      cout << "-1";
   }
return 0;
}

輸出

對於輸入36，上面的C++程式將產生以下輸出：

3

方法2

現在我們將研究一個更有效的解決方案。

• 首先，我們將檢查給定數字是否為完全平方數。

• 如果不是，我們將返回-1。

• 如果它是完全平方數，那麼我們將進一步檢查其平方根是否為三角形數。

• 如果是，則返回根。如果不是，則返回-1。

虛擬碼

Start
check if the Sum is a perfect square
	find the squareRoot of the Sum
	checking if the squareRoot is a triangular number 
	if true
	   then return root
	else 
	   return false
End

示例

下面是一個C++程式，用於檢查給定數字是否等於前n個自然數的立方和。

#include <bits/stdc++.h>
using namespace std;
// Calculates the root of n(n+1)/2 = numif the root is an integer, returns the root else returns -1
int checkTriangularNum(int num){
   if (num < 0){
      return false;
   }
   // Converting the equation n*(n+1)/2 = num in the form of a(n^2) + bn + c = 0";
   int a = 1, b = 1;
   int c = num * (-2);
   int dis = (b * b) - (4 * a * c);
   if (dis < 0) return -1;
   // calculating the roots
   float root1 = ( -b + sqrt(dis)) / (2 * a);
   float root2 = ( -b - sqrt(dis)) / (2 * a);
   // checking if root1 is an integer
   if (root1 > 0 && floor(root1) == root1){
      return root1;
   }
   // checking if root2 is an integer
   if (root2 > 0 && floor(root2) == root2){
      return root2;
   }  
   return -1;
}
// Calculates the square root of the numberreturns the root if it an integer, else returns -1
int checkPerfectSquare(double x){
// floating point value of square root
double squareRoot = sqrt(x);
// checking if the root is integer
if ((squareRoot - floor(squareRoot)) == 0)
   return floor(squareRoot);
else
   return -1;
}
// This function returns n if the sum of cubes of first
// n natural numbers is equal to the given Sum
int calcSquaredTriangularNumber(int Sum){
   // checking if Sum is a perfect square
   int squareRoot = checkPerfectSquare(Sum);
   // if it's not a perfect square return -1
   if (squareRoot == -1)
      return -1;
   // if is a perfect square, then check if it's a
   // triangular number or not
   return checkTriangularNum(squareRoot);
}

int main(){
   int Sum = 36;
   // Function Call
   int n = calcSquaredTriangularNumber(Sum);
   if(n>0){
      cout << n ;
      return n;
   }
   else { 
      cout << "-1";
   }
 return 0;
}

輸出

對於輸入36，上面的C++程式將產生以下輸出：

3