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_i = 1 for all i <= 0;
A_i = A_[i/p]-x + A_[i/q]-y for all i >= 1, where [x] denotes the floor function of x. (see Notes)

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

Definition

Class:: InfiniteSequence2
Method:: calc
Parameters:: long, int, int, int, int
Returns:: long
Method signature:: long calc(long n, int p, int q, int x, int y)
(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^13, inclusive.
p and q will both be between 2 and 10^9, inclusive.
x and y will both be between 0 and 10^9, inclusive.

Examples

10000000

2

3

10000000

10000000

Returns: 2

A[10000000] = A[-5000000] + A[-6666667] = 2.
12

2

3

1

0

Returns: 8
0

2

2

0

0

Returns: 1

A[0] = 1.
123

45

67

8

9

Returns: 2
10000000000000

2

2

0

10131990

Returns: 11993312
10000000000000

2

3

3434343

0

Returns: 1182936
9999999999998

2

2

3000000

0

Returns: 37498466
1234567891011

2

3

0

1000000

Returns: 711689
10000000000000

2

2

1000000000

999999999

Returns: 8192
9999999999999

2

3

1000000000

999999999

Returns: 1369
8335957747793

5

2

10

6

Returns: 50167999
27025202362

9

8

6

0

Returns: 2689
3426365180540

12

7

3

5

Returns: 7446
6429294702567

17

10

0

2

Returns: 3613
3135145174067

9

10

6

4

Returns: 5352
8167369133069

8

2

7

10

Returns: 4493437
7373131176229

18

6

8

7

Returns: 5594
4324734575198

4

7

1

4

Returns: 169441
8980412776091

9

4

6

7

Returns: 75983
7281982906996

6

7

6

7

Returns: 34334
6505572660336

5

7

4

4

Returns: 70498
3895141616124

20

6

2

10

Returns: 4614
364610515434

15

4

4

9

Returns: 8361
7178945117276

15

9

9

6

Returns: 3602
2399752392754

16

8

9

3

Returns: 2883
12943947739

12

10

8

6

Returns: 550
570036140795

9

5

9

5

Returns: 13739
2902376710097

15

10

7

8

Returns: 2149
280959997301

4

9

8

7

Returns: 18466
6619364228444

17

8

0

8

Returns: 4598
5771114738097

17

2

2

4

Returns: 551168
7856631704567

13

2

2

5

Returns: 1290156
4683269455306

6

8

5

0

Returns: 35162
8829112805732

13

3

7

0

Returns: 161652
6715409959708

8

2

4

10

Returns: 4762979
2245117142618

11

8

8

2

Returns: 5769
7488231192379

14

6

1

5

Returns: 11671
1500911165193

6

3

8

8

Returns: 403690
5856008936987

11

8

1

0

Returns: 12288
1936960709859

13

10

4

6

Returns: 2400
5407476153275

20

10

9

7

Returns: 1729
1237239036029

10

10

8

8

Returns: 4096
1011789366143

9

7

8

8

Returns: 7399
5763939964443

6

4

2

4

Returns: 290025
4818909002904

7

7

3

6

Returns: 24576
6996504569917

10

8

0

1

Returns: 16018
5499480298490

17

8

10

8

Returns: 3140
8139544617505

10

3

9

2

Returns: 230579
8464722308542

6

5

5

1

Returns: 160031
8611789376348

285228807

740759357

6939507

933110197

Returns: 2
5568529195746

654887345

34949302

37127827

450573621

Returns: 2
1801447267605

494613813

889023313

87755422

335354339

Returns: 2
8736569229320

346811308

308044881

396473730

745425661

Returns: 2
3416402586708

470503468

977648525

434248626

590079443

Returns: 2
5624473442062

884167640

559412926

188213258

143408281

Returns: 2
5550431419379

273911902

238433455

776532036

238962600

Returns: 2
4930113903881

407487133

707900975

619290071

665947467

Returns: 2
7981058657199

937370165

404158662

711845894

776808932

Returns: 2
9668824272813

472713776

260152961

501252995

642548898

Returns: 2
1340704365084

437116468

850952929

967681094

25187188

Returns: 2
10000000000000

2

2

0

0

Returns: 17592186044416

max answer
10000000000000

2

2

2

2222222

Returns: 44470458
10000000000000

2

2

1234567

0

Returns: 86169543
10000000000000

2

2

0

1100000

Returns: 95846721
10000000000000

2

2

1000000

0

Returns: 104592532
10000000000000

2

2

1

1

Returns: 4398046511104
10000000000000

2

2

0

1000000

Returns: 104592532
10000000000000

2

2

1

4

Returns: 2766178294444
10000000000000

2

2

0

10000000

Returns: 12144693
9999999999999

2

2

1111111

0

Returns: 94972147
10000000000000

2

2

0

5000000

Returns: 23289372
1000000000000

2

3

1

1

Returns: 1893461615
999999999999

2

2

499999

0

Returns: 19949114
10000000000000

2

2

0

100000

Returns: 879148277
10000000000000

2

2

0

400000

Returns: 244787015
999999999999

2

2

0

0

Returns: 1099511627776
2358775268291

2

2

3350

679115

Returns: 13407808
10000000000

2

2

0

0

Returns: 17179869184
10000000000000

2

2

0

123456

Returns: 724865000
10000000000000

2

2

0

500007

Returns: 199182503
10000000000000

2

3

13

17

Returns: 1953326158
10000000000000

2

2

0

2000000

Returns: 54796271
10000000000000

2

2

124342

1138

Returns: 272433069
10000000000000

2

3

1

2

Returns: 9664293228
10000000000000

2

2

1

1000000

Returns: 96791648
10000000000000

2

2

0

3000000

Returns: 37498466
9999999999999

2

2

0

0

Returns: 17592186044416
100000000000

2

2

2

3

Returns: 24230196227
10000000000000

2

2

0

131071

Returns: 686650497
10000000000000

2

2

999973

997

Returns: 49870998
10000000000000

2

2

0

16777216

Returns: 7450599
999173121312

2

2

5

154456

Returns: 47819197
10000000000000

2

2

23000

270000

Returns: 72411191
10000000000000

2

2

1000000

1

Returns: 96791648
10000000000000

2

2

1234567

1

Returns: 79850809
10000000000000

2

2

123456

444

Returns: 330443974
10000000000000

2

3

1

0

Returns: 16010084397
10000000000000

2

2

2345

123797

Returns: 232774981
10000000000000

2

2

123456

0

Returns: 724865000
10000000000000

2

3

0

0

Returns: 24595366566
10000000000000

2

2

2

123321

Returns: 630709045
8796093022208

2

2

0

0

Returns: 17592186044416
10000000000000

2

2

2

2

Returns: 2199023255552
10000000000000

2

2

2

3

Returns: 2199023255552
9999999999999

2

2

1000000

0

Returns: 104592532
10000000000000

2

2

1001

104729

Returns: 322241427
10000000000000

2

2

1

0

Returns: 7800976744450
10000000000000

2

2

12345

324567

Returns: 76283543
10000000000000

2

3

453

345

Returns: 148235861
10000000000000

2

2

0

1

Returns: 7800976744450
9999999999999

2

2

0

182311

Returns: 506394388
10000000000000

2

2

0

390000

Returns: 250633419
10000000000000

2

2

0

390012

Returns: 250626223
10000000000000

2

2

10000000

47

Returns: 8871503
10000000000000

2

2

0

390717

Returns: 250204273
10000000000000

3

2

7

5

Returns: 3829335023
10000000000000

2

2

0

1048575

Returns: 100135912
1234567891011

2

3

0

1

Returns: 3377145969
10000000000000

2

2

0

391717

Returns: 249608366
10000000000000

2

2

0

397717

Returns: 246095851
10000000000000

2

2

1

2

Returns: 3900488372226
10000000000000

2

2

123

1234566

Returns: 54025419
10000000000000

2

2

234512

0

Returns: 401142982
10000000000000

2

2

0

65536

Returns: 1296998106
10000000000000

2

2

3

1757567

Returns: 53867288

Statistics

Problem Statement for "InfiniteSequence2"

Problem Statement

Definition

Notes

Constraints

Examples