#### muutwikaeliaserndafetango

##### New Coder

Hi everyone. I’ve been trying to solve this competitive programming problem but I can’t. Can anyone please help?

Problem Statement:

To achieve this you can perform two types of operations: subtract k from n or divide n by k and round down to the nearest integer. In other words, you can either assign n←n−k or assign n←⌊nk⌋.

What is the minimum number of operations required to make n equal to zero?

Each test contains multiple test cases. The first line of input contains a single integer t — the number of test cases in this test (1≤t≤104).

In the i-th of the following lines two integers n and k for the i-th test case are given (0≤n≤109; 1≤k≤109).

For each test case, output a single integer on a separate line — the minimum number of operations required to make the corresponding n equal to zero.

input

12 1

10 2

137 2

137 12

1024 2

12

3

7

2

10

Problem Statement:

B. Divide or Subtract?

time limit per test

1 second

memory limit per test

1024 megabytes

You are given two integers: n and k. Your goal is to make the number n equal to 0.time limit per test

1 second

memory limit per test

1024 megabytes

To achieve this you can perform two types of operations: subtract k from n or divide n by k and round down to the nearest integer. In other words, you can either assign n←n−k or assign n←⌊nk⌋.

What is the minimum number of operations required to make n equal to zero?

**Input**Each test contains multiple test cases. The first line of input contains a single integer t — the number of test cases in this test (1≤t≤104).

In the i-th of the following lines two integers n and k for the i-th test case are given (0≤n≤109; 1≤k≤109).

**Output**For each test case, output a single integer on a separate line — the minimum number of operations required to make the corresponding n equal to zero.

**Example**input

Copy

512 1

10 2

137 2

137 12

1024 2

**output****Copy**

3

7

2

10

Code:

```
#include <iostream>
using namespace std;
int min_operations(int n, int k) {
int operations = 0;
while (n > 0) {
if (k == 1) {
return n; // Only subtraction is possible.
}
if (n < k) {
operations += n; // Need to subtract k until n becomes 0.
break;
}
int remainder = n % k;
if (remainder != 0) {
n -= remainder;
operations += remainder;
} else {
n /= k;
operations++;
}
}
return operations;
}
int main() {
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
cout << min_operations(n, k) << endl;
}
return 0;
}
```

Last edited by a moderator: