TopCoder problem "KthElement" used in SRM 255 (Division II Level Three)



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.

 

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)
    
0
12
5
Returns: 12
The sequence is 0, 12, 12, 12... and so on.
1)
    
1
7
15
Returns: 9
The sequence is 0, 7, 10, 9, 9, 9... and so on.
2)
    
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.
3)
    
79
4
700000000
Returns: 478
The sequence is 0, 4, 83, 320, 162, 241, 399, 478, 557, 399, 478, 557, 399... and so on.
4)
    
293451
765339
900000000
Returns: 3993300

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4622

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=7228&pm=4622

Writer:

Andrew_Lazarev

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Math, Search