# PROBLEM LINK:

*Author and Editorialist:* Aadarsh A

# DIFFICULTY:

EASY-MEDIUM

# PREREQUISITES:

Arrays, Math, Observation

# PROBLEM:

Given an number N, construct an array such that sum of cubes of the array elements is equal to difference of any 2 perfect squares (p^2 and q^2). Also, the sum of the array should be minimum, and the sum of square roots of the perfect squares is also minimum.

# QUICK EXPLANATION:

The minimum array that can be constructed is [2, 3, 4 .... N+1].

The sum of the square roots is minimum for the array when p and q are \dfrac{(n+1)(n+2)}{2} and 1.

# EXPLANATION:

This problem revolves around the following identity:

n^3 = \left(\dfrac{n(n+1)}{2}\right)^2 - \left(\dfrac{n(n-1)}{2}\right)^2

To satisfy the condition imposed by the question, we can observe that any array with consecutive elements will satisfy the condition.

Example:

For n=3, the array [3,4,5] will satisfy the condition, with 225 and 9 being the perfect squares.

3^3 = 6^2 - 3^2

4^3 = 10^2 - 6^2

5^3 = 15^2 - 10^2

\implies 3^3 + 4^3 + 5^3 = 15^2 - 3^2

So, to obtain minimum possible sum of elements, we need to choose an array of consecutive elements starting from 2 till N-1.

2^3 = 3^2 - 1^2

3^3 = 6^2 - 3^2

4^3 = 10^2 - 6^2

\implies 2^3 + 3^3 + 4^3 = 10^2 - 1^2

It can be also proved that \dfrac{(n+1)(n+2)}{2} and 1 give the minimum possible sum of square roots.

## Proof

Let the sum of cubes obtained from the constructed array be S.

Let the perfect sqaures be p^2 and q^2.

p^2 - q^2 = S

p = \sqrt{S-q^2}

p + q = \sqrt{S-q^2} + q

Since, \sqrt{S-q^2} is an increasing function on q \geq 1.

So, minimum value of q is obtained only at 1.

Hence, the value of p = \sqrt{S-1} = \dfrac{(n+1)(n+2)}{2}

# SOLUTIONS:

## Setter's Solution (C++)

```
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define vi vector<int>
#define pb push_back
#define MOD 1000000007
using namespace std;
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int t; cin >> t;
while (t--) {
int n; cin >> n;
int sum_perfect_sq = ((n+1)*(n+2)/2 + 1)%MOD;
cout << sum_perfect_sq << endl;
for (int i=2; i<=n+1; i++) {
cout << i << " ";
}
cout << endl;
}
}
```