TopCoder Statistics - Problem Statement

Problem Statement

You are given four longs K, N, A and B. Generate an integer list X of length B-A+1 using the following recursive definition:

        X[0]=(K*A) MOD N
	(note that K*A may overflow a 64-bit integer variable)

        X[i]=(X[i-1]+K) MOD N

Given another two longs lower and upper, return the number of elements in the list which are between lower and upper, inclusive.

Definition

Class:: ModuleSequence
Method:: countElements
Parameters:: long, long, long, long, long, long
Returns:: long
Method signature:: long countElements(long K, long N, long A, long B, long lower, long upper)
(be sure your method is public)

Constraints

K will be between 0 and 10,000,000,000, inclusive.
N will be between 1 and 10,000,000,000, inclusive.
A will be between 0 and 10,000,000,000, inclusive.
B will be between A and 10,000,000,000, inclusive.
lower will be between 0 and N-1, inclusive.
upper will be between lower and N-1, inclusive.

Examples

6

4

0

6

1

3

Returns: 3
2

7

1

5

2

5

Returns: 3

The generated list is: 2, 4, 6, 1, 3.
9

1

0

7

0

0

Returns: 8
36

73

1

69

28

34

Returns: 7
30

83

2

24

57

60

Returns: 2
2

30

2

59

27

29

Returns: 4
456

394

11

43

107

259

Returns: 12
919

422

84

538

324

338

Returns: 16
370

316

13

527

100

143

Returns: 72
1873

9957

862

9171

1741

2425

Returns: 572
925

2306

84

6328

1769

2132

Returns: 985
1729

847

313

5858

318

726

Returns: 2656
545

19583

8814

33368

2360

15409

Returns: 16368
13750

44044

1087

26809

19138

21124

Returns: 1172
93584

95789

2652

5403

36533

65948

Returns: 844
95060

999933

49676

993369

10987

342940

Returns: 313283
698586

636227

48094

297540

307314

363239

Returns: 21927
960378

651435

66602

97467

227942

620897

Returns: 18619
3570492

573318

260757

926652

262969

533252

Returns: 313926
3209441

2724287

953865

4429690

1898273

2205701

Returns: 392238
744729

1558441

958031

3108118

633763

1492101

Returns: 1184193
22890675

69834482

120709

91698928

3194229

9936482

Returns: 8841531
24872353

55179498

7254586

72276966

48579743

48737314

Returns: 185670
28624

52406220

51528

40332872

7993292

19518209

Returns: 8858695
515530019

378409504

13258270

573363369

185439195

274731196

Returns: 132166091
631518149

373226341

747796

289700724

168002245

370689936

Returns: 156921378
439493451

150122847

90892921

760243556

30209603

121369018

Returns: 406451209
897617218

1000000000

98172345

987651234

345781920

689102934

Returns: 305376803
20

12

21

30

1

11

Returns: 6

Note that K, A and B may be greater than N.
30

89

112

200

80

88

Returns: 9
890

1000

1000

10000

456

980

Returns: 4770
789817231

1000000000

112130

901030000

10

999999989

Returns: 900917853
67845

999999937

19827119

987123469

198276

987172189

Returns: 954696369
2317

999999937

127890182

589123123

981234

89372612

Returns: 40743198
10000000000

179882778

9

10000000000

482349

66707728

Returns: 3681585348
10000000000

42046

9361

9762861596

756

36321

Returns: 8258231524
36

6074

96

8143895786

5

286

Returns: 378099866
3818987

484373601

8812

9999585582

0

0

Returns: 20
7733999

26882058

1

10000000000

8

778539

Returns: 289608037
66

61

2

2

0

28

Returns: 1
3102916

36698

105

12297

2970

2986

Returns: 7
610

3

0

463

0

0

Returns: 155
0

3

0

9

0

0

Returns: 10
45

4

0

105

0

0

Returns: 27
283

3

978

9574

0

0

Returns: 2866
3

8753

618

56924

8

24

Returns: 107
6

43

0

297

0

2

Returns: 21
4

6

0

0

2

3

Returns: 0
8863

7299

175590

343799

0

5238

Returns: 120734
8229093

6444334183

346

4720366958

65

990216849

Returns: 725317114
122491

61

9

3089

7

9

Returns: 151
96

6327

8

827

0

954

Returns: 122
4

23356376

34592

59850882

0

3190834

Returns: 8740207
0

7

0

3

0

0

Returns: 4
0

19

0

5

0

0

Returns: 6
96740

66

0

8

15

55

Returns: 6
0

580

31

54

325

523

Returns: 0
168

16714

0

65808

0

345

Returns: 1364
938

17075

7144

9758

415

797

Returns: 58
9770

44761

0

10

6

4512

Returns: 1
6

592

1

3

0

7

Returns: 1
0

2

9

28

0

0

Returns: 20
9680

60252

55

99770

0

680

Returns: 1131
0

38

0

1

0

1

Returns: 2
0

76

82

48103

0

0

Returns: 48022
4

816

628

3694347

0

4

Returns: 36212
4431

8

35

7985

0

1

Returns: 1988
15

67

0

6

0

0

Returns: 1
7270

58

90

38005

0

4

Returns: 3923
0

10000000000

0

8041187738

23

393226

Returns: 0
71914641

8219710345

650

3594592

1

81087041

Returns: 35455
10000000000

10000000000

148

1957161979

5

22914188

Returns: 0
18

10000000000

37193769

590733710

161

830151

Returns: 46111
13463

7004183269

31700

51503

23408

96316177

Returns: 0
104587

10000000000

8

448727

21

582915

Returns: 22
0

2358585113

3124645

109468985

0

7233509

Returns: 106344341
0

6972907078

493

592

0

92

Returns: 100
35

10000000000

551404

93378353

761

81802

Returns: 0
263585

3748580475

784

10000000000

6

309921

Returns: 826761
81400091

7891627516

834

986207111

1742

375523920

Returns: 46928514
700345

7638450937

106637

76458819

58

2201346

Returns: 22006
91671

10000000000

1886754595

10000000000

8

55911377

Returns: 45361702
673488

6047147195

1145

17868200

9

83463

Returns: 238
24960757

1525239145

0

7

4668

672158330

Returns: 7
5690

2797706119

5216874

543383007

0

16647

Returns: 3204
713

2953494382

152

2356222934

4889001

51075304

Returns: 36858355
9

10000000000

67

568260

0

75457551

Returns: 568194
8862

10000000000

57

964

57

2020

Returns: 0
0

7434112013

217584

53228528

3149

5717705153

Returns: 0
20559572

2787210882

1074

1885

48658

4083252

Returns: 1
6980

4764566153

0

10000000000

15766833

3049648235

Returns: 6367673720
607781

10000000000

9

97669

741

2680161

Returns: 21
37

10000000000

308277

221192715

9247

64793070

Returns: 1442888
10000000000

10000000000

9055281

6960003866

98538

1123767

Returns: 0
4751107922

1384396066

0

88515774

6505

37610339

Returns: 2404316
97346

2268906990

6234

1385024

3092

748957800

Returns: 455392
59170

6625230692

667

6676

911

28170463

Returns: 0
879596216

5041570717

289

8487699791

89094

8646937

Returns: 14407495
594

3866472085

4992

857855252

67

2240982

Returns: 494210
5538268747

9280620023

439

10000000000

392290

2117107941

Returns: 2280791111
3873832291

9243734047

844008683

8305999347

65051

3945850064

Returns: 3185229126
3066443058

9216962357

9799

9421599602

428372

2255956008

Returns: 2305602998
10000000000

9384639833

115848089

9679657372

2

7553259798

Returns: 7697464942
5395019831

9111685043

8

5814101024

81053244

7746793022

Returns: 4891453695
1401652739

9099070649

652

9042136466

245495877

6363128911

Returns: 6079353676
10000000000

9077365987

6059

10000000000

991

9015994850

Returns: 9932383924
3864996971

9006789191

53

6190180989

7736

5199594409

Returns: 3573568961
10000000000

9697157339

55

10000000000

9662197

3203235427

Returns: 3293308647
10000000000

9289332727

8890961

7764983158

9067637

2915291194

Returns: 2426540040
2405988971

9151501481

99169

6009407091

247

6787619871

Returns: 4457071494
7437275078

9560190569

540328

10000000000

2809466

8458630300

Returns: 8844346650
7446651281

9852474461

9358

10000000000

58569184

5110534923

Returns: 5127606303
3090604069

9557950481

29503

10000000000

43956

7376204016

Returns: 7717280307
9928575098

9038673443

159360161

3714853899

6

6113803058

Returns: 2404953405
3572904435

9028027969

467

8186477087

614844498

2356204718

Returns: 1579038595
10000000000

9241576733

2486

2677159910

99

4922173734

Returns: 1425885788
10000000000

9416544017

829

7959823592

504

1760271363

Returns: 1487960339
5515062957

9584283431

70867266

10000000000

2276

3248094414

Returns: 3364960793
10000000000

9875961727

7

2815210226

0

4853625947

Returns: 1383559179
2699372987

9243625331

698056

10000000000

2157

8320113879

Returns: 9000290074
9231000888

9400594519

680

10000000000

0

7498822204

Returns: 7976965373
10000000000

9345438317

561962

10000000000

7708

3930603934

Returns: 4205661854
6378355110

9144254909

40464

2972407256

2041

6485903516

Returns: 2108261236
5080559190

9667709567

9158129

10000000000

85

3110837967

Returns: 3214814145
10000000000

9679470391

8450025456

10000000000

5071546561

7461383579

Returns: 382684832
10000000000

9797407289

166567856

10000000000

1881547

8647732885

Returns: 8677641950
10000000000

9206563987

1678681913

8292854073

807138848

7586316523

Returns: 4870291276
10000000000

9807421177

233075

8436291959

78461972

4398821109

Returns: 3716247464
10000000000

9439683751

4722000

1786391879

14

5581785716

Returns: 1053520409
9214971511

9875961727

1000000000

9000000000

2500000000

7500000000

Returns: 4050238448

anti Yarin's approach (almost no benefit)
9812648090

9875961727

2500000000

7500000000

2500000000

7500000000

Returns: 2531399040
3141592653

6234566789

1

5235252355

252353255

2362436161

Returns: 1771865935
9342439234

8422544562

7934923495

8324943292

32556456

934556456

Returns: 41768595
2234567891

10000000000

7

10000000000

1234567890

9876543219

Returns: 8641975325
7154141414

9999999997

728738462

2227971615

888917

9918107716

Returns: 1486822325
10000000000

10000000000

1000000000

10000000000

0

9999999999

Returns: 9000000001

Statistics

Problem Statement for "ModuleSequence"

Problem Statement

Definition

Constraints

Examples