TopCoder Statistics - Problem Statement

Problem Statement

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

You are given two geometric progressions S1 = (b1*q1ⁱ, 0 <= i <= n1-1) and S2 = (b2*q2ⁱ, 0 <= i <= n2-1). Return the number of distinct integers that belong to at least one of these progressions.

Definition

Class:: GeometricProgressions
Method:: count
Parameters:: int, int, int, int, int, int
Returns:: int
Method signature:: int count(int b1, int q1, int n1, int b2, int q2, int n2)
(be sure your method is public)

Constraints

b1 and b2 will each be between 0 and 500,000,000, inclusive.
q1 and q2 will each be between 0 and 500,000,000, inclusive.
n1 and n2 will each be between 1 and 100,500, inclusive.

Examples

3

2

5

6

2

5

Returns: 6

The progressions in this case are (3, 6, 12, 24, 48) and (6, 12, 24, 48, 96). There are 6 integers that belong to at least one of them: 3, 6, 12, 24, 48 and 96.
3

2

5

2

3

5

Returns: 9

This time the progressions are (3, 6, 12, 24, 48) and (2, 6, 18, 54, 162). Each of them contains 5 elements, but integer 6 belongs to both progressions, so the answer is 5 + 5 - 1 = 9.
1

1

1

0

0

1

Returns: 2

The progressions are (1) and (0).
3

4

100500

48

1024

1000

Returns: 100500

Each element of the second progression belongs to the first progression as well.
15724

19169

26501

6334

18467

42

Returns: 26543
28145

5705

24465

26962

29358

11479

Returns: 35944
11942

2995

492

9961

16827

23282

Returns: 23774
153

3902

14605

32391

5436

4828

Returns: 19433
19895

19718

18717

17421

12382

293

Returns: 19010
19912

1869

11539

14771

21726

5448

Returns: 16987
23811

28703

9895

17035

26299

25668

Returns: 35563
7711

15141

4665

17673

30333

31323

Returns: 35988
32757

32662

27645

25547

6868

28254

Returns: 55899
778

27529

9742

8723

12859

20038

Returns: 29780
6

8

1843

0

5

12317

Returns: 1844
5

6

22649

4

2

9041

Returns: 31690
1

6

15351

0

9

15891

Returns: 15352
4

4

12624

9

8

24394

Returns: 37018
8

1

7377

6

0

18757

Returns: 3
8

7

11324

6

9

16945

Returns: 28269
5

3

16542

9

2

16119

Returns: 32661
6

7

9931

4

8

4640

Returns: 14571
2

4

28746

1

6

31674

Returns: 60420
2

7

15574

7

9

6271

Returns: 21845
7

5

18637

1

0

23987

Returns: 18639
0

0

12053

1

4

23656

Returns: 23657
1

7

3431

6

4

16942

Returns: 20373
3

3

12288

7

7

18008

Returns: 30296
8

1

9759

9

9

14946

Returns: 14947
8

3

13031

6

6

6423

Returns: 19453
9

0

1656

2

1

901

Returns: 3
1

5

6484

8

7

27625

Returns: 34109
0

4

30837

1

0

3603

Returns: 2
4

8

23200

8

1

4597

Returns: 23201
938

6418

2000

53

4734

8282

Returns: 10282
893

3728

468

127

3788

6901

Returns: 7369
617

4310

2422

807

2483

24649

Returns: 27071
451

8935

7617

309

9514

22814

Returns: 30431
303

2798

31557

519

5249

20601

Returns: 52158
702

4989

32610

844

1008

6225

Returns: 38835
587

523

14344

93

485

3196

Returns: 17540
618

3458

25201

448

9503

29315

Returns: 54516
798

9589

15282

798

9796

20581

Returns: 35862
292

8538

23623

472

7157

28010

Returns: 51633
191

7958

29658

190

4179

6039

Returns: 35697
634

6202

11512

156

2888

19816

Returns: 31328
886

6362

22647

328

55

24273

Returns: 46920
416

3844

20143

869

8433

18876

Returns: 39019
699

21

18652

322

1998

21882

Returns: 40534
712

5075

24390

892

8476

3558

Returns: 27948
688

7861

26870

3

2510

2601

Returns: 29471
585

5002

16424

255

9789

13402

Returns: 29826
757

8617

31427

88

285

24183

Returns: 55610
189

5721

2155

169

932

9833

Returns: 11988
555

1425

100408

368

1329

100424

Returns: 200832
60

145

100488

441

6549

100466

Returns: 200954
996

6279

100477

139

3753

100482

Returns: 200959
949

9866

100463

549

2529

100413

Returns: 200876
105

8286

100484

297

3195

100407

Returns: 200891
701

8114

100466

455

6282

100412

Returns: 200878
355

4313

100437

786

671

100484

Returns: 200921
945

1832

100492

912

53

100415

Returns: 200907
982

3646

100442

321

7756

100487

Returns: 200929
161

7129

100478

196

4144

100419

Returns: 200897
659

2044

100434

173

450

100465

Returns: 200899
510

6154

100476

253

6439

100408

Returns: 200884
22

4474

100487

186

649

100455

Returns: 200942
391

7958

100495

787

4018

100432

Returns: 200927
824

9314

100486

477

3625

100498

Returns: 200984
70

1833

100441

372

5874

100466

Returns: 200907
270

7773

100423

518

8297

100413

Returns: 200836
480

3102

100415

192

2668

100437

Returns: 200852
625

527

100401

802

7627

100487

Returns: 200888
181

3061

100428

23

1924

100457

Returns: 200885
64361782

278265998

13032

404190149

398909281

31004

Returns: 44036
7731313

467628530

30975

273962893

258886387

13065

Returns: 44040
88331384

4601214

12551

152935541

344122576

19712

Returns: 32263
153311297

69235394

26303

210891650

69658576

28020

Returns: 54323
17776006

91768487

23153

432729471

335060730

23852

Returns: 47005
234755061

394647782

30228

165691496

155909546

9011

Returns: 39239
184483000

86041627

14475

114291593

59903613

7883

Returns: 22358
334102285

122467277

24597

490274939

434550262

25424

Returns: 50021
210101195

450663219

20327

265950118

270669882

1265

Returns: 21592
111530245

161894771

21764

489059820

205197150

21154

Returns: 42918
353874983

376079536

13008

76004269

80438542

30901

Returns: 43909
148862018

191845671

5109

76159309

418139037

2304

Returns: 7413
420609636

19473952

6541

397338317

234933697

14461

Returns: 21002
279393325

53290125

23217

474665036

461759623

6073

Returns: 29290
416729352

470499968

13023

462114144

262567997

29338

Returns: 42361
230625183

214934244

4566

290683301

287799911

11586

Returns: 16152
238331539

203117345

16973

474330366

55814400

12054

Returns: 29027
72865406

153203338

22849

381265747

81363855

2608

Returns: 25457
53312702

105563598

17826

161115859

213375189

23755

Returns: 41581
53667750

399552958

22702

70119943

41489194

15206

Returns: 37908
1112

2

6963

1112

2

1994

Returns: 6963
2700

8

24856

2400

3

14414

Returns: 39269
611

8

1753

2444

4

30878

Returns: 31755
16152

8

20073

5384

24

10041

Returns: 30113
17

8

13170

136

216

14933

Returns: 28102
1464

9

2590

1464

9

28686

Returns: 28686
22592

27

22045

353

4

19315

Returns: 41359
3795

3

12182

759

5

11193

Returns: 23374
4650

3

17550

2325

6

20609

Returns: 38158
10032

4

31241

2508

4

6468

Returns: 31242
601

16

8214

38464

24

6078

Returns: 14292
601

16

26429

9616

6

23393

Returns: 49821
75

5

6288

1800

5

18787

Returns: 25075
108648

24

2364

12072

36

21222

Returns: 23586
105624

6

7620

17604

216

18241

Returns: 23321
5346

9999

75617

5346

1000

2252

Returns: 77868
495

100000

63296

5000

9999

34269

Returns: 97565
4653

100000

53594

469953

9999

8917

Returns: 62511
2277

10

52640

2300000

10

86141

Returns: 138781
5742

100000

41957

58000000

1000

25563

Returns: 67520
9000

100000

69738

9000

10

55623

Returns: 114236
28000

9999

84972

279972

10

28807

Returns: 113778
62000

1000

85713

6200000

1000

75266

Returns: 160979
13000

99

10584

13000000

9999

43275

Returns: 53859
499950

100000

88

499950

10

16699

Returns: 16699
529947

1000

37915

5300000

9999

8834

Returns: 46749
89991

9999

4768

9000000

100000

14049

Returns: 18817
200000

9999

5279

200000

10

63668

Returns: 68946
6400000

9999

23852

64000000

99

2076

Returns: 25928
33000000

10

81207

33000000

10

2250

Returns: 81207
10976

2744

45557

10976

2744

96680

Returns: 96680
7448

196

47246

104272

14

33675

Returns: 64084
117992

2744

14835

117992

196

74301

Returns: 81718
8820

2744

63077

8820

2744

76235

Returns: 76235
10780

2744

55754

150920

196

28491

Returns: 74748
178360

14

53742

178360

2744

24228

Returns: 60056
1008

24

61280

1008

624

75218

Returns: 136497
144

624

20117

744

3125

97215

Returns: 117332
624

124

49697

16224

5

90283

Returns: 139980
864

24

17984

112500

24

92447

Returns: 110431
1344

124

61448

874944

24

92520

Returns: 153968
6820

5

53526

6820

24

54693

Returns: 108218
3100

24

59073

15600

124

12562

Returns: 71635
6200

124

31062

156250

3125

32684

Returns: 63746
1984

124

66702

249984

624

21792

Returns: 88494
33696

624

42772

33696

3125

78913

Returns: 121684
29952

3125

81331

150000

124

12644

Returns: 93975
17472

5

50578

437472

5

63960

Returns: 114538
156250

5

35714

156250

24

45797

Returns: 81510
237500

624

10688

1187424

3125

44712

Returns: 55400
1390536

624

92028

1390536

124

40965

Returns: 132992
499999999

0

100500

500000000

500000000

100500

Returns: 100502
499999999

0

100500

500000000

0

100500

Returns: 3
499999999

1

100500

500000000

500000000

100500

Returns: 100501
499999999

1

100500

500000000

1

100500

Returns: 2
500000000

1

100500

500000000

500000000

100500

Returns: 100500
500000000

1

100500

500000000

1

100500

Returns: 1
499999999

499999999

100500

500000000

500000000

100500

Returns: 201000
499999998

500000000

100500

499999999

499999999

100500

Returns: 201000
446185740

410498683

100500

268953270

164601714

100500

Returns: 201000

22 primes involved
1

274684395

100500

251020324

255002404

100500

Returns: 201000
1

493335308

100500

90742056

43867919

100500

Returns: 201000
1000007

1000007

100500

1000009

1000009

100000

Returns: 200500
33554430

33554432

100500

33554431

33554432

100500

Returns: 201000
4194304

4194304

100500

4194303

4194304

100500

Returns: 201000
4194304

4194304

100500

4194304

4194304

100500

Returns: 100500
11

0

100500

15

61

10516

Returns: 10518
11

1

11021

54

84

15468

Returns: 15469
65415

46845

46515

54684

0

46558

Returns: 46517
7

4

5

8

0

1

Returns: 6
12

0

1

42

31

1

Returns: 2
1

247256567

100500

33883938

19096233

100500

Returns: 201000
15

5

20

3

25

50

Returns: 60
3

4

100500

48

102499

100000

Returns: 200499
500000000

500000000

100500

500000000

500000000

100500

Returns: 100500
499999999

499999999

100500

499999997

499999997

100500

Returns: 201000
8

4

10500

16

64

10500

Returns: 21000
500000000

500000000

100000

500000000

500000000

100000

Returns: 100000
9

108

10300

36

4

1100

Returns: 11400
500000000

500000000

45

35

67

78

Returns: 123
100000000

200000000

10500

300000000

150000000

10400

Returns: 20900
500000000

500000000

13333

500000000

500000000

13333

Returns: 13333
499999999

99999999

99

499292939

391989849

30

Returns: 129
510510

510510

100500

485100

485100

100500

Returns: 201000
499999999

499999977

100500

499999799

499999997

100500

Returns: 201000
30

30

100000

6

150

100000

Returns: 199999
1000000

1000000

100500

1000000

1000000

100500

Returns: 100500
400000000

400000000

99

400000000

400000000

400

Returns: 400
400

210

100500

2

210

100500

Returns: 201000
499999999

499999999

100000

499999999

499999999

100000

Returns: 100000
500000000

500000000

100500

499999999

500000000

100500

Returns: 201000
0

0

100300

0

0

100300

Returns: 1
30

77

10000

33

70

500

Returns: 10499
499999997

499999999

100489

499999999

499999997

100499

Returns: 200987
400000000

400000000

100000

400004235

213421323

100001

Returns: 200001
500000000

50000000

10050

3650

100000000

65

Returns: 10115
483229421

483228817

100500

483231491

483229387

100500

Returns: 201000
12

1581

100400

151

3

100100

Returns: 200500
500000000

499999999

100500

498765432

499999998

100500

Returns: 201000
477777777

50000000

100500

5000000

477777777

100000

Returns: 200500
499999999

498765432

100500

412345678

398765421

100500

Returns: 201000
12

53

1005

12

106

100500

Returns: 101504
500000000

500000000

100500

49999999

49999999

100499

Returns: 200999
200

20000

100500

197

15478

100500

Returns: 201000
478296791

18234627

100500

478296787

12415135

100500

Returns: 201000
3

4

100500

48

1024

100500

Returns: 180900
500000000

455454545

100000

445448488

465656644

100000

Returns: 200000
1

0

1

2

0

1

Returns: 2
100

10000000

12356

957813

97626322

10953

Returns: 23309
1

1

1

1

0

1

Returns: 1
1

1000000

100500

1

1000

100500

Returns: 150750
17

2

100499

19

7

100245

Returns: 200744
500000000

500000000

100500

499999999

499999999

100500

Returns: 201000
6

6

100500

4

4

100500

Returns: 201000
0

1

100500

2

0

100500

Returns: 2
1

1

10000

1

1

99999

Returns: 1
8

1

100

8

1

200

Returns: 1
3

3

50000

2

2

50000

Returns: 100000
498792878

298191928

100000

222828721

9878282

100098

Returns: 200098
499999999

499999999

100500

499999999

399999999

100500

Returns: 200999
1

1

10000

1

1

9000

Returns: 1
200

500000000

100500

197

490000000

100500

Returns: 201000
2

16

100500

64

2

100500

Returns: 175875
1

4

100500

1

4

100500

Returns: 100500
499000011

499000011

100000

499000013

499000013

100100

Returns: 200100
495104921

500000000

100500

495104551

376554347

100123

Returns: 200623
500000000

99999999

100500

500000000

99992399

100400

Returns: 200899
500000000

500000000

100000

499999999

500000000

99999

Returns: 199999
0

2

10

0

3

20

Returns: 1
1

0

1000

10

0

1200

Returns: 3
151581151

89

100500

141362197

83

100500

Returns: 201000
0

100500

100500

0

100500

100500

Returns: 1
3

1

100217

5

1

100207

Returns: 2
1

0

100500

1

1

100499

Returns: 2

Statistics

Problem Statement for "GeometricProgressions"

Problem Statement

Definition

Constraints

Examples