Statistics

Problem Statement for "DivideAndShift"

Problem Statement

Manao is playing a game called "Divide and Shift". There is a sequence of N slots in the game numbered from 1 to N. Initially each of them contains an object. Manao's goal is to obtain the object which is initially in slot M. At any time of the game, he can only obtain an object that is in slot 1 at that time.

Manao can perform two types of moves. The first is choosing a prime number p which divides N and dividing the sequence of the slots in p contiguous subsequences, namely the slots from 1 to N/p, the slots from N/p+1 to 2N/p, etc. Then, Manao keeps the subsequence which contains the desired object and gets rid of the remaining slots. The length of the chosen subsequence is then assigned to N and the slots in it are renumbered from 1 to the new value of N.

The second type of move is shifting the objects in the slots. Manao can perform a left shift and a right shift. After a left shift, for each i &gt 1 the object in slot i is moved to slot i-1 and the object in slot 1 is moved to the last slot of the sequence. After a right shift, each object is moved to the slot to the right and the object in the last slot is moved to slot 1.

Determine the least number of moves in which Manao can reach the goal. Taking the object from slot 1 is not considered a move.

Definition

Class:
DivideAndShift
Method:
getLeast
Parameters:
int, int
Returns:
int
Method signature:
int getLeast(int N, int M)
(be sure your method is public)

Notes

  • A positive integer number is called prime if it has exactly two divisors - 1 and itself. For example, 2, 3, 5 and 7 are prime numbers, and 4, 6, 8 and 9 are not prime. By convention, 1 is not considered to be a prime number.
  • A prime number p divides N if the ratio N/p is an integer.

Constraints

  • N will be between 1 and 1,000,000, inclusive.
  • M will be between 1 and N, inclusive.

Examples

  1. 56

    14

    Returns: 3

    One possible way to obtain the object in slot 14 is to perform the following operations: 1. Divide by 2. N becomes equal to 28 now. 2. Shift right. The object moves to slot 15. 3. Divide by 2 again. The sequence 15..28 is kept, renumbered as 1..14 and the object appears in slot 1.

  2. 49

    5

    Returns: 2

    Manao divides by 7 twice and gets a single slot.

  3. 256

    7

    Returns: 6

    Shift left until the object is in slot 1.

  4. 1

    1

    Returns: 0

  5. 7

    3

    Returns: 1

  6. 6

    1

    Returns: 0

    The object may be in slot 1 right in the beginning.

  7. 93

    13

    Returns: 1

  8. 256

    255

    Returns: 2

  9. 1000000

    1234

    Returns: 9

  10. 123456

    12347

    Returns: 7

  11. 999999

    215

    Returns: 6

  12. 999999

    234625

    Returns: 5

  13. 3

    2

    Returns: 1

  14. 2

    2

    Returns: 1

  15. 4

    3

    Returns: 1

  16. 5

    3

    Returns: 1

  17. 8

    6

    Returns: 2

  18. 9

    6

    Returns: 2

  19. 12

    11

    Returns: 2

  20. 14

    8

    Returns: 1

  21. 15

    9

    Returns: 2

  22. 16

    11

    Returns: 3

  23. 16

    12

    Returns: 3

  24. 27

    23

    Returns: 3

  25. 32

    11

    Returns: 4

  26. 32

    12

    Returns: 4

  27. 32

    16

    Returns: 2

  28. 35

    29

    Returns: 1

  29. 100

    58

    Returns: 3

  30. 108

    6

    Returns: 4

  31. 512

    13

    Returns: 7

  32. 4096

    666

    Returns: 10

  33. 5096

    776

    Returns: 4

  34. 10000

    6123

    Returns: 6

  35. 6144

    20

    Returns: 11

  36. 6144

    63

    Returns: 8

  37. 8192

    4110

    Returns: 12

  38. 19999

    521

    Returns: 2

  39. 19945

    229

    Returns: 2

  40. 25998

    15633

    Returns: 3

  41. 59049

    12157

    Returns: 9

  42. 59049

    57851

    Returns: 10

  43. 59049

    59045

    Returns: 5

  44. 524288

    55022

    Returns: 18

  45. 524288

    625

    Returns: 15

  46. 200000

    47237

    Returns: 9

  47. 173734

    58450

    Returns: 4

  48. 360216

    6327

    Returns: 5

  49. 360216

    284234

    Returns: 3

  50. 1000000

    1

    Returns: 0

  51. 1000000

    999999

    Returns: 2

  52. 1000000

    964998

    Returns: 8

  53. 1000000

    631233

    Returns: 6

  54. 1000000

    718118

    Returns: 11

  55. 1000000

    66

    Returns: 7

  56. 1000000

    999593

    Returns: 9

  57. 999999

    33

    Returns: 6

  58. 999999

    999999

    Returns: 1

  59. 999999

    96495

    Returns: 6

  60. 969696

    696696

    Returns: 5

  61. 999983

    427

    Returns: 1

  62. 510510

    44128

    Returns: 6

  63. 510510

    362585

    Returns: 6

  64. 881790

    61

    Returns: 4

  65. 881790

    428

    Returns: 6

  66. 881790

    17290

    Returns: 3

  67. 881790

    337156

    Returns: 2

  68. 881790

    337151

    Returns: 5

  69. 881790

    337152

    Returns: 6

  70. 5184

    1367

    Returns: 7

  71. 972000

    44

    Returns: 12

  72. 972000

    277634

    Returns: 7

  73. 972000

    324044

    Returns: 12

  74. 408484

    31267

    Returns: 2

  75. 637377

    636123

    Returns: 4

  76. 999954

    233632

    Returns: 3

  77. 676892

    123456

    Returns: 3

  78. 356478

    183526

    Returns: 4

  79. 876542

    123537

    Returns: 1

  80. 964999

    488425

    Returns: 3

  81. 524288

    27

    Returns: 18

  82. 360360

    4374

    Returns: 7

  83. 77777

    11111

    Returns: 2

  84. 997920

    508988

    Returns: 10

  85. 997920

    97115

    Returns: 11

  86. 1000000

    806790

    Returns: 11

  87. 1000000

    100012

    Returns: 11

  88. 1000000

    42354

    Returns: 9

  89. 362880

    77777

    Returns: 9

  90. 1000000

    1000000

    Returns: 1

  91. 418944

    161799

    Returns: 8

  92. 345534

    234139

    Returns: 3

  93. 7

    1

    Returns: 0

  94. 984712

    302000

    Returns: 3

  95. 999983

    500000

    Returns: 1

  96. 999947

    336327

    Returns: 2

  97. 720720

    462363

    Returns: 7

  98. 600

    67

    Returns: 4

  99. 786432

    222222

    Returns: 18

  100. 169

    7

    Returns: 2

  101. 987524

    254782

    Returns: 3

  102. 147456

    127523

    Returns: 13

  103. 999983

    1515

    Returns: 1

  104. 786432

    24606

    Returns: 17

  105. 13

    5

    Returns: 1

  106. 11

    5

    Returns: 1

  107. 1000000

    100

    Returns: 9

  108. 12

    5

    Returns: 1

  109. 1000000

    100000

    Returns: 3

  110. 3000

    2001

    Returns: 1

  111. 10

    5

    Returns: 1

  112. 999983

    999982

    Returns: 1

  113. 77

    75

    Returns: 2

  114. 55997

    20000

    Returns: 1

  115. 100

    100

    Returns: 1

  116. 53

    42

    Returns: 1

  117. 200006

    100004

    Returns: 1

  118. 127

    5

    Returns: 1

  119. 125

    8

    Returns: 3

  120. 997920

    22222

    Returns: 9

  121. 20

    14

    Returns: 2

  122. 1000000

    123456

    Returns: 7

  123. 1000000

    14

    Returns: 11

  124. 200

    2

    Returns: 1

  125. 1000000

    598432

    Returns: 8

  126. 6

    3

    Returns: 1

  127. 524288

    11111

    Returns: 18

  128. 100003

    19

    Returns: 1

  129. 700001

    350000

    Returns: 1

  130. 77

    8

    Returns: 1

  131. 161051

    123

    Returns: 4

  132. 999983

    444444

    Returns: 1

  133. 324

    19

    Returns: 3

  134. 590340

    59

    Returns: 3

  135. 1000000

    985421

    Returns: 9

  136. 8

    2

    Returns: 1

  137. 333101

    257733

    Returns: 1

  138. 999958

    499979

    Returns: 1

  139. 5098

    1219

    Returns: 1

  140. 999999

    123457

    Returns: 6

  141. 999983

    555555

    Returns: 1

  142. 7

    7

    Returns: 1

  143. 720720

    86719

    Returns: 7

  144. 9

    9

    Returns: 1

  145. 15

    4

    Returns: 1

  146. 65

    6

    Returns: 1

  147. 524288

    262044

    Returns: 18

  148. 6

    4

    Returns: 1

  149. 524288

    524288

    Returns: 1

  150. 523673

    10000

    Returns: 1

  151. 17

    5

    Returns: 1

  152. 2

    1

    Returns: 0

  153. 71

    5

    Returns: 1

  154. 10007

    5000

    Returns: 1

  155. 8

    8

    Returns: 1

  156. 84822

    58094

    Returns: 3

  157. 33

    13

    Returns: 1

  158. 80640

    11

    Returns: 10

  159. 68

    4

    Returns: 2

  160. 147

    147

    Returns: 1

  161. 100003

    12345

    Returns: 1

  162. 899197

    123934

    Returns: 3

  163. 1000000

    15724

    Returns: 11

  164. 524288

    524270

    Returns: 18

  165. 531441

    531411

    Returns: 12

  166. 987584

    675947

    Returns: 7

  167. 999997

    65537

    Returns: 2

  168. 500000

    102020

    Returns: 9

  169. 524288

    1934

    Returns: 18

  170. 18

    5

    Returns: 2

  171. 983557

    343

    Returns: 1

  172. 55

    6

    Returns: 1

  173. 931327

    889286

    Returns: 2

  174. 362880

    123456

    Returns: 7

  175. 391

    18

    Returns: 1

  176. 1001

    1000

    Returns: 2

  177. 524287

    123456

    Returns: 1

  178. 198273

    128376

    Returns: 4

  179. 4199

    18

    Returns: 2

  180. 8

    4

    Returns: 2

  181. 7

    4

    Returns: 1

  182. 524288

    50

    Returns: 16

  183. 87

    85

    Returns: 1

  184. 510510

    1991

    Returns: 5

  185. 200006

    3

    Returns: 1

  186. 997920

    111111

    Returns: 10

  187. 524288

    523066

    Returns: 17

  188. 510510

    30031

    Returns: 1

  189. 5706

    5322

    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: