TopCoder Statistics - Problem Statement

Problem Statement

Consider a circle in the plane.

You are given an int places. This is the number of places that are equally spaced along the perimeter of the circle, i.e., the distance between any two consecutive places is equal. The places are numbered 0 to places-1 in clockwise order, starting at an arbitrary place.

We will now draw red points in some of the places. The number of red points is given as an int points. As the number of points may be large, we will generate them using a simple process that is described below.

Finally, once all points are generated, your task is to find and return the number of right triangles that have all three vertices in red points.

To generate the points, you are given three ints a, b, and c. For n = 0, 1, 2, 3, ..., points-1, execute the following steps:

Compute P[n] = (a*n*n + b*n + c) modulo places.
Starting at P[n], find the first place in the clockwise direction that does not contain a red point.
Put a red point onto that place.

Definition

Class:: RightTriangle
Method:: triangleCount
Parameters:: int, int, int, int, int
Returns:: long
Method signature:: long triangleCount(int places, int points, int a, int b, int c)
(be sure your method is public)

Notes

A right triangle is a triangle with non-zero area in which one of the angles is exactly 90 degrees.
For any valid input the answer fits into a long (i.e., a signed 64-bit integer variable).

Constraints

places will be between 1 and 1,000,000, inclusive.
points will be between 0 and 100,000, inclusive.
points will not be greater than places.
a will be between 0 and 1,000,000, inclusive.
b will be between 0 and 1,000,000, inclusive.
c will be between 0 and 1,000,000, inclusive.

Examples

9

3

0

3

0

Returns: 0

The points are placed on places 0, 3, and 6. The resulting triangle is not a right triangle (in fact, it is equilateral).
40

3

5

0

0

Returns: 1

This time the red points are on places 0, 5, and 20. The only triangle determined by these points is a right triangle.
4

4

16

24

17

Returns: 4

This time the formula for the next place always gives the output 1. Hence the points are placed on places 1, 2, 3, and 0, in this order. Each of the four triangles determined by these points is a right triangle.
1000000

47000

0

2

5

Returns: 0

An awful lot of obtuse triangles.
100000

100000

0

0

987654

Returns: 4999900000
1000000

100000

123

456

789

Returns: 2016259674
100008

100000

123

456

789

Returns: 4999500008
10

9

1664

2346

3346

Returns: 28
100020

99999

0

2

21312

Returns: 4998750033
200000

700

123456

789012

345678

Returns: 6980

Watch out for integer overflow when computing P[n].
987654

98765

0

493827

132451

Returns: 4877114466
200000

100000

800000

100000

77777

Returns: 4999900000

similar to #10, but a is positive (is somebody compares just with 0, it fails)
1000000

100000

500000

500000

123456

Returns: 0
109998

100000

15714

47142

241444

Returns: 4500009998
109998

92342

31428

47142

214223

Returns: 3448252620
131072

100000

16384

65536

45

Returns: 3446331072
97432

84640

580490

104276

344495

Returns: 3097666162
115778

74501

370212

113967

950802

Returns: 2536765449
68579

6175

981761

976111

140183

Returns: 0
143389

97930

372964

568534

346801

Returns: 0
96922

38264

245957

807322

818015

Returns: 638860614
54290

46095

628387

787168

707493

Returns: 1037230779
140063

68247

346734

951535

219120

Returns: 0
586936

79415

164585

274339

155313

Returns: 2089197204
60935

56060

691959

422247

359266

Returns: 0
141873

84815

690435

850522

545852

Returns: 0
633631

9948

683863

116463

244060

Returns: 0
114440

1628

973128

224770

808092

Returns: 104064
47058

27953

899432

384474

408342

Returns: 220002321
94903

36493

838091

612688

42522

Returns: 0
148537

58109

296802

146423

856454

Returns: 0
57842

56265

197686

969796

844441

Returns: 1538905576
135130

82440

678194

600187

145531

Returns: 2842132488
103489

51879

867634

374459

1022

Returns: 0
91241

60602

425976

411640

257603

Returns: 0
115415

85712

892818

263260

978073

Returns: 0
5375

986

693003

994488

191972

Returns: 0
124939

82501

769582

974304

135493

Returns: 0
26835

2904

825323

212071

732386

Returns: 0
16273

6551

670878

113447

235655

Returns: 0
57844

2783

224597

179507

477657

Returns: 0
40742

6139

472789

186244

867370

Returns: 7714209
137075

59919

241668

438589

208733

Returns: 0
121731

58696

403773

142774

8810

Returns: 0
28911

14718

618390

102626

166550

Returns: 0
119341

49547

167591

683434

153601

Returns: 0
38049

4258

885995

144776

472190

Returns: 0
36452

290

552887

34186

894654

Returns: 0
791761

89855

390699

374746

68048

Returns: 0
144401

9373

980441

739989

833666

Returns: 0
105446

80148

125598

487561

330543

Returns: 2835004458
601663

80118

219643

490284

605673

Returns: 0
118434

27623

773881

373622

19585

Returns: 150037272
30970

17324

446288

902610

828784

Returns: 80322114
100145

77935

921952

428803

579454

Returns: 0
43406

27595

30356

606678

728994

Returns: 243315074
77471

47905

793504

335163

539877

Returns: 0
108412

3736

929434

96990

376773

Returns: 0
15685

13474

239237

355992

642185

Returns: 0
134063

67906

350197

992899

331460

Returns: 0
56005

8517

777967

946148

33235

Returns: 0
57773

35060

813983

809209

863200

Returns: 0
112995

61118

387329

826606

226700

Returns: 0
108243

93711

595168

49845

709473

Returns: 0
129948

46163

814937

131369

905219

Returns: 907756065
16441

8855

297853

261551

208073

Returns: 0
902917

86639

867712

967540

463169

Returns: 0
116519

60048

383502

939737

827346

Returns: 0
141196

64003

476527

749571

410188

Returns: 1911837872
694603

75976

664839

75055

492182

Returns: 0
17976

2782

670123

704411

110180

Returns: 2449180
133550

43750

652632

86544

150564

Returns: 299805044
73416

38562

379052

520642

621732

Returns: 726200480
36692

24572

44796

781965

783153

Returns: 245208600
25670

8931

528233

631578

685173

Returns: 35269550
121183

48257

461164

722948

506887

Returns: 0
123456

54321

123455

123455

213313

Returns: 1314302524
1

0

3

2

1

Returns: 0
1000000

100000

0

0

0

Returns: 0
102346

100000

0

0

47

Returns: 4882602346
1

1

21421

435

354

Returns: 0
2

2

32

42

24

Returns: 0
3

3

142

14

144

Returns: 0
8

3

1

3

4

Returns: 1
557056

21525

16384

24576

4144

Returns: 231458342
120000

46332

0

48000

245214

Returns: 0
120000

66532

0

48000

35432

Returns: 434573960
117276

37635

0

337

324

Returns: 707199336
117276

97645

0

348

3535

Returns: 3808760501
131070

100000

999983

998989

99907

Returns: 3753924920
150000

100000

900000

600000

415641

Returns: 2499950000
100000

100000

100000

100000

100000

Returns: 4999900000
100000

100000

0

0

0

Returns: 4999900000
100000

100000

0

0

1

Returns: 4999900000
1000000

100000

0

500000

0

Returns: 4999900000
100000

100000

100000

100000

0

Returns: 4999900000
150000

100000

0

0

0

Returns: 2499950000
110000

100000

0

0

0

Returns: 4499910000
1000000

100000

1000000

1000000

1000000

Returns: 0
100002

100000

0

0

0

Returns: 4999800002
10

10

1

1

1

Returns: 40
100000

60000

0

0

0

Returns: 599980000
1000000

10000

0

0

0

Returns: 0
1000000

100000

0

0

1

Returns: 0
100006

100000

0

0

4398

Returns: 4999600006
199998

100000

0

0

0

Returns: 99998
1000000

100000

0

0

5

Returns: 0
100400

100000

0

0

0

Returns: 4979900400
999998

9999

99919

9992

23215

Returns: 309907
100000

100000

0

0

50000

Returns: 4999900000
1000000

100000

0

0

999999

Returns: 0
100000

100000

0

100000

0

Returns: 4999900000
1000000

100000

12311

131241

421423

Returns: 1441971160
123456

100000

0

0

0

Returns: 3827123456
1000000

100000

0

0

100

Returns: 0
100000

100000

0

0

1000

Returns: 4999900000
1000000

99999

2192

129817

276756

Returns: 1010769676
1000000

100000

0

0

4

Returns: 0
100000

100000

100000

0

0

Returns: 4999900000
99

56

13

69

13

Returns: 0
8

8

1023

1000000

1024

Returns: 24
5

5

0

0

1

Returns: 0
11

11

0

0

0

Returns: 0
1000000

98000

99991

9993

99998

Returns: 1507209240
1000000

100000

12324

4234

7658

Returns: 1805663886
99999

99999

0

0

0

Returns: 0
199999

99999

123456

789012

345678

Returns: 0
1000000

100000

0

1000000

0

Returns: 0
1000000

99999

0

0

0

Returns: 0
1000000

100000

0

999999

999999

Returns: 0
100006

100000

0

50003

4398

Returns: 4999900000
100000

100000

12362

62361

37273

Returns: 4999900000
1000000

100000

999999

999999

999999

Returns: 1800963980
4

4

1

6

4

Returns: 4
999999

99999

99999

99999

1233

Returns: 0
4

3

1

0

0

Returns: 1
427140

53954

800199

697862

878322

Returns: 71108736

Statistics

Problem Statement for "RightTriangle"

Problem Statement

Definition

Notes

Constraints

Examples