Selfreference | Topcoder Archive

Problem Statement

In this problem we will investigate a class of self-referencing functions.

Given is a positive integer K>1. We will now define a function F. The function is defined on non-negative integers, and it is uniquely determined by the following two properties:

F is strictly increasing. That is, for all X, F(X+1) > F(X).
For all X, F(...F(F(X))...) = K*X, where F is applied K-1 times in a row.

For example, for K=4 the first few values of F are shown in the table below. You can see, for example, that F(F(F(2))) = F(F(3)) = F(4) = 8 = K*2.

  N    0   1   2   3   4   5   6   7   8
F(N)   0   2   3   4   8   9  10  11  12

You will be given a non-negative integer N encoded as a String, and a positive integer K. Write a method that computes F(N).

Definition

Class:: Selfreference
Method:: getValue
Parameters:: String, int
Returns:: long
Method signature:: long getValue(String N, int K)
(be sure your method is public)

Notes

You may assume that the output will always fit into a long.

Constraints

N will contain an integer between 0 and 1015, inclusive.
N will not contain unnecessary leading zeroes.
K will be between 2 and 1,000, inclusive.

Examples

```
"47"
```
```
2
```
```
Returns: 94
```
For K=2 the condition for F simplifies to F(X)=2X.
```
"5"
```
```
4
```
```
Returns: 9
```
This is one of the values shown in the problem statement.
```
"8"
```
```
4
```
```
Returns: 12
```
```
"17"
```
```
3
```
```
Returns: 26
```
```
"1234567890123"
```
```
47
```
```
Returns: 1741191010586
```

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.