TopCoder Statistics - Problem Statement

Problem Statement

You are given four ints: n, k, x, and y.

The ints n and k describe a simple undirected graph. The graph has n nodes, numbered 1 through n. Two distinct vertices i and j are connected by an edge if and only if gcd(i, j) > k. Here, gcd(i, j) denotes the greatest common divisor of i and j.

The ints x and y are the numbers of two (not necessarily distinct) vertices in our graph. Return "Possible" if it is possible to travel from x to y by following the edges of our graph. Otherwise, return "Impossible".

In other words, return "Possible" if our graph contains a path that connects the nodes x and y, and "Impossible" if there is no such path.

Definition

Class:: GCDGraph
Method:: possible
Parameters:: int, int, int, int
Returns:: String
Method signature:: String possible(int n, int k, int x, int y)
(be sure your method is public)

Constraints

n will be between 2 and 1,000,000, inclusive.
k will be between 0 and n, inclusive.
x and y will be between 1 and n, inclusive.

Examples

12

2

8

9

Returns: "Possible"

We have a graph with n = 12 nodes. As k = 2, vertices i and j are connected by an edge if and only if gcd(i, j) is strictly greater than 2. In this graph it is possible to travel from node 8 to node 9. One possible path: 8 -> 4 -> 12 -> 9.
12

2

11

12

Returns: "Impossible"

This is the same graph as in Example 0, but now we are interested in another pair of nodes. It is not possible to travel from node 11 to node 12. In particular, in our graph node 11 is an isolated node because for any other node x we have gcd(11, x) = 1.
12

2

11

11

Returns: "Possible"

A node is always reachable from itself.
10

2

8

9

Returns: "Impossible"
1000000

1000

12345

54321

Returns: "Possible"
1000000

2000

12345

54321

Returns: "Impossible"
2

0

1

2

Returns: "Possible"
1000000

100

123456

111111

Returns: "Possible"
1000000

10000

111111

123456

Returns: "Impossible"
523532

333

1213

42823

Returns: "Possible"
523532

444

1213

42823

Returns: "Impossible"
917463

910

31503

119431

Returns: "Impossible"
896657

8

715200

104300

Returns: "Possible"
728443

2

56844

659814

Returns: "Possible"
506671

79

255568

258666

Returns: "Impossible"
333171

80

311297

226873

Returns: "Impossible"
837677

6357

215805

412920

Returns: "Impossible"
326813

81990

131976

67062

Returns: "Impossible"
100033

2583

37951

78039

Returns: "Impossible"
758382

931

622425

69311

Returns: "Impossible"
741771

586669

294181

45502

Returns: "Impossible"
517876

302

508937

244308

Returns: "Impossible"
698521

1

35534

96176

Returns: "Possible"
595003

91

305339

224349

Returns: "Impossible"
696023

42745

519341

107582

Returns: "Impossible"
997896

0

776983

581034

Returns: "Possible"
99164

42303

63427

828

Returns: "Impossible"
914825

8

749795

849827

Returns: "Possible"
773946

44

184283

14444

Returns: "Possible"
927108

1678

857255

222980

Returns: "Impossible"
79041

58

75594

23300

Returns: "Possible"
805597

2

197716

101927

Returns: "Possible"
943228

894427

116788

460042

Returns: "Impossible"
110693

9

90490

90668

Returns: "Possible"
236960

68

226377

224483

Returns: "Impossible"
395719

241878

22265

116152

Returns: "Impossible"
541911

3

471050

475494

Returns: "Possible"
493515

31608

288206

28910

Returns: "Impossible"
183008

7

70437

57007

Returns: "Possible"
260471

804

174820

228078

Returns: "Impossible"
259126

835

134591

148583

Returns: "Impossible"
147198

114

44121

127576

Returns: "Possible"
824285

3084

516875

308884

Returns: "Impossible"
438629

94553

41188

258085

Returns: "Impossible"
268564

45449

4188

161482

Returns: "Impossible"
889639

644228

92884

846436

Returns: "Impossible"
25284

9601

22385

14597

Returns: "Impossible"
1707

726

738

1231

Returns: "Impossible"
144530

74

118538

135947

Returns: "Impossible"
352476

85

175272

68008

Returns: "Impossible"
647523

8993

553861

112237

Returns: "Impossible"
565485

52109

4863

207394

Returns: "Impossible"
418094

843

266825

90476

Returns: "Impossible"
439816

2882

211557

123216

Returns: "Impossible"
344019

94970

93886

339051

Returns: "Impossible"
92099

4885

28105

60323

Returns: "Impossible"
282236

137739

13944

26094

Returns: "Impossible"
795883

9

722956

96560

Returns: "Possible"
719981

10

309724

40678

Returns: "Impossible"
196501

62053

41308

148739

Returns: "Impossible"
805556

8985

734397

178909

Returns: "Impossible"
931536

218

508781

306464

Returns: "Impossible"
930383

5

820764

736413

Returns: "Impossible"
623964

12905

433894

150563

Returns: "Impossible"
178058

127790

148488

67978

Returns: "Impossible"
527813

15040

9712

268075

Returns: "Impossible"
732476

248738

202543

652393

Returns: "Impossible"
337393

211285

128440

55733

Returns: "Impossible"
612992

92

579197

522840

Returns: "Impossible"
608227

1

528470

536506

Returns: "Possible"
848338

125

795480

631091

Returns: "Impossible"
320215

8461

183795

151464

Returns: "Impossible"
303944

914

169675

79638

Returns: "Impossible"
875821

10

110200

415206

Returns: "Possible"
478068

1910

302310

390315

Returns: "Impossible"
338575

842

299442

266993

Returns: "Impossible"
665858

270

345505

424137

Returns: "Possible"
279194

0

122647

194890

Returns: "Possible"
515336

423

432623

274521

Returns: "Impossible"
961258

1

341913

510452

Returns: "Possible"
620575

68275

581091

264897

Returns: "Impossible"
973688

356

141920

118088

Returns: "Possible"
439005

98097

380545

9935

Returns: "Impossible"
687457

953

124219

606007

Returns: "Impossible"
137451

26581

129040

11834

Returns: "Impossible"
541430

87628

312224

171079

Returns: "Impossible"
99299

37045

46065

81262

Returns: "Impossible"
478645

2497

316463

278260

Returns: "Impossible"
956904

418

503010

180945

Returns: "Impossible"
818079

137613

244388

106677

Returns: "Impossible"
436802

510

384322

54866

Returns: "Impossible"
48312

26388

11950

45848

Returns: "Impossible"
94202

69

9414

44243

Returns: "Possible"
89502

77571

53750

37208

Returns: "Impossible"
519715

6955

85580

211153

Returns: "Impossible"
795316

4

52075

97762

Returns: "Possible"
879952

162

807238

393385

Returns: "Impossible"
411144

369

266955

22326

Returns: "Possible"
116724

8

68260

10263

Returns: "Possible"
497822

6

482888

143696

Returns: "Possible"
760104

9

41890

121866

Returns: "Possible"
588812

33019

123386

96379

Returns: "Impossible"
910316

68782

621773

418642

Returns: "Impossible"
105270

98411

99497

15074

Returns: "Impossible"
788634

42012

736334

726682

Returns: "Impossible"
86589

9

56012

7457

Returns: "Possible"
874876

908

333947

15632

Returns: "Impossible"
960476

2978

560598

316832

Returns: "Impossible"
284772

293

17688

162825

Returns: "Possible"
393023

272067

346007

392973

Returns: "Impossible"
447100

915

43471

220685

Returns: "Impossible"
10

5

2

2

Returns: "Possible"
3

1

1

3

Returns: "Impossible"
10

10

9

9

Returns: "Possible"
1000000

100

500000

500001

Returns: "Impossible"
10

10

7

7

Returns: "Possible"
891264

205744

187866

857333

Returns: "Impossible"

Statistics

Problem Statement for "GCDGraph"

Problem Statement

Definition

Constraints

Examples