Statistics

Problem Statement for "NonCoprimeGraph"

Problem Statement

Two positive integers are called coprime (or relatively prime) if their greatest common divisor is 1. For example, 10 and 21 are coprime, but 15 and 21 are not coprime as they are both divisible by 3.

Let G be a simple undirected graph with the following properties:
  • G has n vertices, numbered 1, 2, ..., n.
  • For each pair (i,j) such that i != j, the vertices i and j are connected by an edge if and only if the numbers i and j are not coprime.

You are given the int n. You are also given ints s and t. Find and return the length of the shortest path between the vertices s and t. If there is no such path, return -1 instead.

Definition

Class:
NonCoprimeGraph
Method:
distance
Parameters:
int, int, int
Returns:
int
Method signature:
int distance(int n, int s, int t)
(be sure your method is public)

Constraints

  • n will be between 1 and 1,000,000,000, inclusive.
  • s will be between 1 and n, inclusive.
  • t will be between 1 and n, inclusive.

Examples

  1. 10

    8

    9

    Returns: 2

    The numbers 8 and 9 are coprime, thus there is no direct edge between the vertices 8 and 9. There is a unique shortest path of length 2: the path 8 - 6 - 9.

  2. 10

    6

    9

    Returns: 1

    The numbers 6 and 9 are both divisible by 3. As they are not coprime, there is a direct edge between the vertices 6 and 9. Obviously, this edge is the shortest path that connects 6 and 9.

  3. 100

    89

    97

    Returns: -1

  4. 100

    97

    97

    Returns: 0

  5. 1

    1

    1

    Returns: 0

  6. 100

    1

    2

    Returns: -1

  7. 7

    1

    3

    Returns: -1

  8. 3

    1

    2

    Returns: -1

  9. 2

    1

    2

    Returns: -1

  10. 9

    8

    1

    Returns: -1

  11. 10

    6

    10

    Returns: 1

  12. 4

    2

    4

    Returns: 1

  13. 8

    6

    4

    Returns: 1

  14. 5

    2

    4

    Returns: 1

  15. 6

    2

    3

    Returns: 2

  16. 6

    4

    3

    Returns: 2

  17. 7

    3

    2

    Returns: 2

  18. 10

    2

    3

    Returns: 2

  19. 10

    9

    5

    Returns: 3

  20. 10

    5

    3

    Returns: 3

  21. 10

    3

    5

    Returns: 3

  22. 10

    5

    3

    Returns: 3

  23. 24

    6

    19

    Returns: -1

  24. 64

    25

    41

    Returns: -1

  25. 49

    26

    47

    Returns: -1

  26. 3

    1

    2

    Returns: -1

  27. 72

    18

    64

    Returns: 1

  28. 40

    15

    35

    Returns: 1

  29. 32

    6

    2

    Returns: 1

  30. 68

    55

    50

    Returns: 1

  31. 10

    3

    4

    Returns: 2

  32. 56

    33

    50

    Returns: 2

  33. 86

    50

    57

    Returns: 2

  34. 46

    7

    8

    Returns: 2

  35. 67

    31

    63

    Returns: 3

  36. 49

    13

    19

    Returns: 3

  37. 94

    47

    43

    Returns: 3

  38. 48

    39

    17

    Returns: 3

  39. 574

    153

    349

    Returns: -1

  40. 548

    190

    509

    Returns: -1

  41. 410

    112

    379

    Returns: -1

  42. 108

    30

    107

    Returns: -1

  43. 939

    170

    874

    Returns: 1

  44. 47

    21

    7

    Returns: 1

  45. 779

    526

    442

    Returns: 1

  46. 102

    65

    26

    Returns: 1

  47. 952

    400

    707

    Returns: 2

  48. 913

    636

    211

    Returns: 2

  49. 377

    172

    139

    Returns: 2

  50. 46

    27

    7

    Returns: 2

  51. 580

    179

    209

    Returns: 3

  52. 366

    265

    113

    Returns: 3

  53. 502

    193

    321

    Returns: 3

  54. 466

    323

    113

    Returns: 3

  55. 85630

    20267

    55837

    Returns: -1

  56. 56315

    32327

    33165

    Returns: -1

  57. 59446

    43481

    20010

    Returns: -1

  58. 31425

    29999

    20389

    Returns: -1

  59. 77027

    30201

    17142

    Returns: 1

  60. 61186

    34916

    22924

    Returns: 1

  61. 60655

    41002

    25220

    Returns: 1

  62. 85768

    10448

    48770

    Returns: 1

  63. 27062

    26427

    24902

    Returns: 2

  64. 78369

    23515

    47243

    Returns: 2

  65. 94658

    89248

    73723

    Returns: 2

  66. 13285

    7840

    13269

    Returns: 2

  67. 23496

    20045

    9337

    Returns: 3

  68. 41361

    17173

    20123

    Returns: 3

  69. 87536

    30241

    38947

    Returns: 3

  70. 50099

    6689

    10867

    Returns: 3

  71. 319923

    219799

    203433

    Returns: -1

  72. 9574290

    4842407

    2870035

    Returns: -1

  73. 2011593

    1984907

    100143

    Returns: -1

  74. 8395167

    6928643

    6189449

    Returns: -1

  75. 9545823

    1965526

    3022234

    Returns: 1

  76. 4329013

    3362694

    3899366

    Returns: 1

  77. 1324826

    841570

    428298

    Returns: 1

  78. 1821074

    624082

    1388552

    Returns: 1

  79. 3372058

    1648345

    715796

    Returns: 2

  80. 7174058

    1604089

    5411459

    Returns: 2

  81. 9050878

    4172351

    2392609

    Returns: 2

  82. 3267590

    2125790

    348733

    Returns: 2

  83. 136724

    56033

    44087

    Returns: 3

  84. 7530390

    1271051

    681139

    Returns: 3

  85. 3695347

    1772333

    3012397

    Returns: 3

  86. 1364842

    497993

    259129

    Returns: 3

  87. 848021038

    458015743

    728566018

    Returns: -1

  88. 18173091

    9434119

    15473471

    Returns: -1

  89. 969839413

    484890565

    637940053

    Returns: -1

  90. 83397393

    36531893

    58352923

    Returns: -1

  91. 244165344

    234535224

    128366686

    Returns: 1

  92. 622713217

    80062570

    484686390

    Returns: 1

  93. 654634235

    47338950

    339795762

    Returns: 1

  94. 23400413

    15290948

    19343606

    Returns: 1

  95. 335230263

    104150917

    201985671

    Returns: 2

  96. 462677423

    27761159

    310749010

    Returns: 2

  97. 649390661

    234717367

    619456887

    Returns: 2

  98. 428074160

    417317218

    367217047

    Returns: 2

  99. 231768563

    108490409

    38626329

    Returns: 3

  100. 308142430

    46625791

    62750269

    Returns: 3

  101. 519362889

    180810221

    308900717

    Returns: 3

  102. 636914887

    217452689

    272118507

    Returns: 3

  103. 1000000000

    1

    1

    Returns: 0

  104. 1000000000

    99999997

    99999997

    Returns: 0

  105. 1000000000

    998812807

    997170059

    Returns: 2

  106. 1000000000

    159999929

    209999893

    Returns: 3

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: