KthElement | Topcoder Archive

Problem Statement

Let the function F(N) be a number of ones in the binary representation of the number N. For example F(279)=5 because 279 = (100010111)₂.

The sequence X is constructed using the following rules. The initial element X₀ is 0, and each successive elements X_i is A * F(X_i-1) + B.

You will be given integers A, B and K. Your method should return the X_K element. See examples for further explanation.

Definition

Class:: KthElement
Method:: find
Parameters:: int, int, int
Returns:: int
Method signature:: int find(int A, int B, int K)
(be sure your method is public)

Constraints

A will be between 0 and 1000000, inclusive.
B will be between 0 and 1000000, inclusive.
K will be between 1 and 1000000000, inclusive.

Examples

```
0
```
```
12
```
```
5
```
```
Returns: 12
```
The sequence is 0, 12, 12, 12... and so on.
```
1
```
```
7
```
```
15
```
```
Returns: 9
```
The sequence is 0, 7, 10, 9, 9, 9... and so on.
```
15
```
```
21
```
```
500000001
```
```
Returns: 51
```
The sequence is 0, 21, 66, 51, 81, 66, 51, 81, 66... and so on. The sequence has a period of length 3 starting from X2, so the 500000001th element will be the same as the element with index (500000001 - 2) mod 3 + 2.
```
79
```
```
4
```
```
700000000
```
```
Returns: 478
```
The sequence is 0, 4, 83, 320, 162, 241, 399, 478, 557, 399, 478, 557, 399... and so on.
```
293451
```
```
765339
```
```
900000000
```
```
Returns: 3993300
```

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.