TopCoder Statistics - Problem Statement

Problem Statement

NOTE: This problem statement contains subscripts that may not display properly if viewed outside of the applet.

Let's consider an infinite sequence A defined as follows:

A₀ = 1;
A_i = A_[i/p] + A_[i/q] for all i >= 1, where [x] denotes the floor function of x. (see Notes)

You will be given n, p and q. Return the n-th element of A (index is 0-based).

Definition

Class:: InfiniteSequence
Method:: calc
Parameters:: long, int, int
Returns:: long
Method signature:: long calc(long n, int p, int q)
(be sure your method is public)

Notes

[x] denotes the floor function of x which returns the highest integer less than or equal to x. For example, [3.4] = 3, [0.6] = 0.

Constraints

n will be between 0 and 10^12, inclusive.
p and q will both be between 2 and 10^9, inclusive.

Examples

0

2

3

Returns: 1

A[0] = 1.
7

2

3

Returns: 7

A[0] = 1; A[1] = A[0] + A[0] = 2; A[2] = A[1] + A[0] = 2 + 1 = 3; A[3] = A[2] + A[1] = 3 + 2 = 5; A[7] = A[3] + A[2] = 5 + 3 = 8.
10000000

3

3

Returns: 32768
256

2

4

Returns: 89
1

1000000

1000000

Returns: 2
1000000000000

2

2

Returns: 1099511627776
1000000000000

2

3

Returns: 4266563557
1000000000000

3

3

Returns: 67108864
1000000000000

2

1000000000

Returns: 96
1000000000000

1000000000

1000000000

Returns: 4
987654321234

2

3

Returns: 4135435417
1000000000000

2

4

Returns: 267914296
692777636915

846930888

4289385

Returns: 4
885386760492

424238337

157747795

Returns: 4
202362490027

289641423

596516651

Returns: 4
897763513926

202520061

783368692

Returns: 4
89172455736

640383428

465180542

Returns: 4
702567956429

521595370

35005213

Returns: 4
722862665123

861021532

336465784

Returns: 4
513929979802

468703137

345174069

Returns: 4
133069898167

635723060

415634024

Returns: 4
175011478042

289018458

159961395

Returns: 4
484421544919

753377375

231176231

Returns: 4
575198594324

756898539

608413786

Returns: 4
566413803526

238664372

149798317

Returns: 4
759956241873

524268982

412776093

Returns: 4
906996497281

42999172

137806864

Returns: 4
477084336327

284420927

511702307

Returns: 4
750846621729

259126507

572660338

Returns: 4
616124353895

533925859

200661315

Returns: 4
898814233367

201100547

39819584

Returns: 4
344043313750

685990366

610515436

Returns: 4
117276947178

356426810

577171089

Returns: 4
705403502651

709393586

880695790

Returns: 4
999932095060

574612401

752392756

Returns: 4
947739210012

43993370

511549678

Returns: 4
348094297539

849698588

855636228

Returns: 4
651434960378

463480572

136140797

Returns: 4
710097612902

92066603

317097469

Returns: 4
926652260756

603570494

430573319

Returns: 4
724286209441

485560282

59997303

Returns: 4
228444346619

894429691

294953867

Returns: 4
958031108117

270744731

221558442

Returns: 4
834481890675

207905773

314738099

Returns: 4
704567777856

791698929

710120711

Returns: 4
254586276965

524872355

355179499

Returns: 4
406219028624

803964685

269455308

Returns: 4
805732048829

240332873

160051530

Returns: 4
258270363368

515530021

378409505

Returns: 4
226340518149

277486717

509959710

Returns: 4
142618002245

289700725

200747798

Returns: 4
892921243555

439493453

150122848

Returns: 4
537764888228

722597490

331192381

Returns: 4
165193441500

438792352

347469843

Returns: 4
470124324914

116087766

342757036

Returns: 4
373743346491

182275858

8936989

Returns: 4
709859281936

841148367

350322229

Returns: 4
316437899228

286452553

771151434

Returns: 4
901474276121

213975409

576153277

Returns: 4
36029661237

330794397

653468860

Returns: 4
65818894428

450573795

705908237

Returns: 4
335928639529

187231013

889366145

Returns: 4
11111111110

2

2

Returns: 17179869184
999999999999

2

2

Returns: 1099511627776
999999999999

2

3

Returns: 4266563557
1000000000000

13

3

Returns: 102737
100000000000

2

3

Returns: 673272766
1000000000000

4325435

2

Returns: 212
10000001111

3

2

Returns: 110809534
99999999999

2

3

Returns: 673272766
100000000000

2

2

Returns: 137438953472
999999998127

2

3

Returns: 4266563557
1000000000000

2

1000000

Returns: 252
99999989999

2

3

Returns: 673272766
1000000000000

3

7

Returns: 585167
99999999999

2

2

Returns: 137438953472
1000000000

2

2

Returns: 1073741824
1000000000000

103

1007

Returns: 37
1000000000000

500

600000

Returns: 13
90000001111

3

2

Returns: 615975622

Statistics

Problem Statement for "InfiniteSequence"

Problem Statement

Definition

Notes

Constraints

Examples