CarryAOne | Topcoder Archive

Problem Statement

From primary school we all know how to add two positive integers: we start with the rightmost digits and proceed to the left. During the addition a carry is a digit that is transferred from a column of digits to the next column of more significant digits. For example, when 6 and 7 are added to make 13, the "3" is written to the same column as 6 and 7, and the "1" is carried to the left.

Sometimes the whole addition can be performed without any carries. For example, there are no carries when we compute 123 + 456.

Sometimes the carry can happen when adding together the most significant digits of the two numbers. For example, when adding 305 and 702 we get a carry from the hundreds to the thousands, producing the result 1007.

Addition in other bases is performed in exactly the same way as in decimal (base 10). There can also be carries. For example, in base 16:

When calculating "425 + 777 = ?" we there is no carry and we get the sum "B9C". (Remember that these are all base-16 numbers, with digits 'A'-'F' having values 10-15. The number "425" in base 16 has the value 4*16*16 + 2*16 + 5 = 1061 in base 10.)
When calculating "1A + 1A = ?" there is one carry (from units to sixteens) and we get the sum "34".
When calculating "A30 + 690 = ?" there is one carry (from the order 16^2 to the order 16^3) and we get the sum "10C0".

------------------------------------------------------

Katka is a teacher. She is currently teaching her kids about addition in base B. She would like to give them some non-trivial problems for practice. Each of these problems should have the following properties:

The problem should be of the form "X + Y = ?", where both X and Y are positive integers with exactly D digits (when written in base B).
When computing the addition (still in base B) there must be at least one carry.

How many such problems are there? Calculate and return their number.

Definition

Class:: CarryAOne
Method:: count
Parameters:: int, int
Returns:: long
Method signature:: long count(int B, int D)
(be sure your method is public)

Notes

Order matters. If X and Y are distinct, "X + Y = ?" and "Y + X = ?" are two distinct problems.
For the constraints given below it is guaranteed that the answer fits into a signed 64-bit integer.

Constraints

B will be between 2 and 10^6, inclusive.
D will be between 1 and 20, inclusive.
B to the power of D will not exceed 10^9.

Examples

```
10
```
```
1
```
```
Returns: 45
```
We are in base 10 and we want 1-digit addition problems that involve a carry. Some of these include "4 + 6 = ?", "6 + 4 = ?", "7 + 8 = ?", "1 + 9 = ?", and "9 + 9 = ?". The problems "3 + 4 = ?" and "0 + 7 = ?" are not suitable: in these problems there is no carry, and additionally in the second problem X is not positive.
```
2
```
```
5
```
```
Returns: 256
```
In base 2 the five-digit numbers are the numbers with decimal values between 16 ("10000" in base 2) and 31 ("11111" in base 2), inclusive. There are exactly 16 of them. In base 2 each of the 16*16 possible pairs (X, Y) is a good pair: their sum is always a 6-digit number in base 2, so there is always at least one step in which we carry a one - from the order 2^4 to the order 2^5.
```
6
```
```
3
```
```
Returns: 27990
```
All numbers in this annotation are written in base 6. Some of the good problems include: "120 + 140 = ?" (we carry the one 1x, result is "300") "404 + 404 = ?" (we carry the one 2x, result is "1212") "555 + 554 = ?" (we carry the one 3x, result is "1553") On the other hand, the following problems are not good: "120 + 135 = ?" (there are no carries, result is "255") "055 + 344 = ?" ("055" is not a three-digit number in base 6, it's just a 2-digit number)

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.