平方三角形数（立方和）

---

平方三角形数，也称为三角平方数，是一个既是三角形数又是完全平方数的数。

平方三角形数有无限多个可能的值；前几个是：

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