Intermediate.
Put your skills to the test.

Problem summary

Row r of a triangular arrangement contains j(r−j+1) at column j, for 1≤j≤r. Find the sum of the first row containing a given value a.

Constraints

1 < a < 1000000.

Worked example

Input and output for the worked example discussed below.

6

20

Solution analysis

1. Reading the columns in the diagram gives column j as j,2j,3j,… starting at row j. Therefore cell (r,j) is j(r−j+1). If it equals a, then j and r−j+1 are a factor pair of a.
2. A factor pair d and a/d places a in row d+a/d−1. Enumerate divisors d≤√a and take the smallest such row. This is much faster than constructing all rows up to a.
3. The row sum is Σ j(r+1−j) = r(r+1)(r+2)/6. For a=6, factor pairs (1,6) and (2,3) give rows 6 and 4. Row 4 is [4,6,6,4], and its sum is 20.

Why it works

Every occurrence of a corresponds to one positive factor pair, and every factor pair creates an occurrence in its derived row. The minimum over all pairs is therefore the earliest row. Summing the closed cell formula yields the displayed cubic expression.

Watch out. Do not confuse the row with the factor itself. The answer can exceed int even though a is small; promote before multiplying the three row factors.

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
using namespace std;
int main(){
    long long value;
    cin>>value;
    long long row=value;
    // Factor pairs enumerate all possible appearances of the value.
    for(long long divisor=1;divisor*divisor<=value;divisor++){
        if(value%divisor==0){
            row=min(row,divisor+value/divisor-1);
        }
    }
    cout<<row*(row+1)*(row+2)/6<<'\n';
}