Engineer bro!

Sun Oct 31 2021 (11 months ago)

Engineer by mistake!

I am a software engineer by passion

# Solving a basic number theory problem with c++

You are given two numbers, $D\mathrm{&}ND \& N$. You have to find $sum\left(N\right)sum\left(N\right)$ applied $DD$ times.

(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\left(N\right)sum\left(N\right)$. But today, like a true explorer, he defined his own new function: $sum\left(D,N\right)sum\left(D, N\right)$, 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\left(2,3\right)sum\left(2, 3\right)$ equals to $sum\left(sum\left(3\right)\right)=sum\left(1+2+3\right)=sum\left(6\right)=21sum\left(sum\left(3\right)\right) = sum\left(1 + 2 + 3\right) = sum\left(6\right) = 21$.

Tuzik wants to calculate some values of the $sum\left(D,N\right)sum\left(D, N\right)$ 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\left(N\right)sum\left(N\right)$ because from basic mathematics we already know the formula. The Sum of numbers from $11$ to $NN$ is $\frac{n\ast \left(n+1\right)}{2}\frac\left\{n*\left(n+1\right)\right\}\left\{2\right\}$.

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

But, here we just don't have to calculate $sum\left(n\right)sum\left(n\right)$, 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\left(3\right)sum\left(3\right)$ $1+2+31+2+3$ $66$
2 $sum\left(sum\left(3\right)\right)=sum\left(6\right)sum\left(sum\left(3\right)\right) = sum\left(6\right)$ $1+2+3+4+5+61+2+3+4+5+6$ $2121$

Here, we can see that we just need to call native $sum\left(n\right)sum\left(n\right)$ 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\left(d\ast t\right)O\left(d*t\right)$, $O\left(d\right)O\left(d\right)$ per test case

• Space - $O\left(1\right)O\left(1\right)$

Want to try the solution

C++