Solving a basic number theory problem with c++

You are given two numbers, . You have to find $$sum(N)sum(N)$$ applied $$DD$$ times.

• Problem description

  • Input

  • Output

  • Constraints

  • Sample Input 1

  • Sample Output 1

• Explanation

• Complexity

• Thank You ❤️

(TOC generated by @dsabyte)

Problem description

Yesterday, puppy Tuzik learned a magically efficient method to find the sum of the integers from $$11$$ to $$NN$$. He denotes it as $$sum(N)sum(N)$$. But today, like a true explorer, he defined his own new function: $$sum(D,N)sum(D,\; N)$$, which means the operation sum applied $$DD$$ times: the first time to $$NN$$ and each subsequent time to the result of the previous operation.

For example, if $$D=2D\; =\; 2$$ and $$N=3N\; =\; 3$$, then $$sum(2,3)sum(2,\; 3)$$ equals to $$sum(sum(3))=sum(1+2+3)=sum(6)=21sum(sum(3))\; =\; sum(1\; +\; 2\; +\; 3)\; =\; sum(6)\; =\; 21$$.

Tuzik wants to calculate some values of the $$sum(D,N)sum(D,\; N)$$ function. Will you help him with that?

Input

The first line contains a single integer T, the number of test cases. Each test case is described by a single line containing two integers D and N.

Output

For each test case, output one integer on a separate line.

Constraints

• $$1\le T\le 161\; \le \; T\; \le \; 16$$

• $$1\le D,N\le 41\; \le \; D,\; N\; \le \; 4$$

Sample Input 1

2
1 4
2 3

Sample Output 1

10
21

Explanation

The problem will be simple if we just have to calculate $$sum(N)sum(N)$$ because from basic mathematics we already know the formula. The Sum of numbers from $$11$$ to $$NN$$ is $$\frac{n\ast (n+1)}{2}\backslash frac\{n*(n+1)\}\{2\}$$.

Using the above formula, we can find sum of the numbers from $$11$$ to $$NN$$ in just $$O(1)O(1)$$ time.

But, here we just don't have to calculate $$sum(n)sum(n)$$, we have to repeat it $$DD$$ times.

Let's dry run one of the above examples, $$D=2,N=3D=2,\; N=3$$.

Iteration	Function call	Numbers	Result
1	$$sum(3)sum(3)$$	$$1+2+31+2+3$$	$$66$$
2	$$sum(sum(3))=sum(6)sum(sum(3))\; =\; sum(6)$$	$$1+2+3+4+5+61+2+3+4+5+6$$	$$2121$$

Here, we can see that we just need to call native $$sum(n)sum(n)$$ function $$DD$$ times with the initial value of $$NN$$.

int main() {
    int t;
    cin >> t;
    while (t--) {
        int d, n;
        cin >> d >> n;

        int ans = n; // initialize and as n
        for (int i = 0; i < d; i++) {
            ans = (ans * (ans + 1)) / 2;
        }

        cout << ans << endl;
    }
    return 0;
}

Complexity

• Time - $$O(d\ast t)O(d*t)$$, $$O(d)O(d)$$ per test case

• Space - $$O(1)O(1)$$

Want to try the solution

Thank You ❤️