KthElement
SRM 255 · 2005-07-28 · by Andrew_Lazarev
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)2.
The sequence X is constructed using the following rules. The initial element X0 is 0, and each successive elements Xi is A * F(Xi-1) + B.
You will be given integers A, B and K. Your method should return the XK element. See examples for further explanation.
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.
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
Submissions are judged against all 110 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class KthElement with a public method int find(int A, int B, int K) · 110 test cases · 2 s / 256 MB per case