Statistics

Problem Statement for "TheKingsFactorization"

Problem Statement

The King of Byteland likes integer factorization. Your task is to help him factor the number N. You will be given the long N and you should return a long[] containing all prime factors of N sorted in non-decreasing order. Note that some primes may occur multiple times in the prime factorization of N. For example, for N = 60 the only correct return value is {2, 2, 3, 5} because 2*2*3*5 = 60.

To make this task easier, the King has decided to give you a hint. He already knows the correct factorization and he will tell you every second number in the correct return value. More precisely, in addition to N you will be given a long[] primes. The number of elements in primes will be (M+1)/2, rounded down, where M is the number of elements in the correct return value. For each valid i, primes[i] will be equal to the element 2i of the correct return value. (All indices are 0-based.)

Given N and primes, return the long[] containing the factorization of N.

Definition

Class:
TheKingsFactorization
Method:
getVector
Parameters:
long, long[]
Returns:
long[]
Method signature:
long[] getVector(long N, long[] primes)
(be sure your method is public)

Constraints

  • N will be between 2 and 1,000,000,000,000,000,000 (10^18), inclusive.
  • primes will contain the correct prime factors (as defined in the problem statement).

Examples

  1. 12

    {2, 3}

    Returns: {2, 2, 3 }

  2. 7

    {7}

    Returns: {7 }

  3. 1764

    {2, 3, 7}

    Returns: {2, 2, 3, 3, 7, 7 }

  4. 49

    {7}

    Returns: {7, 7 }

  5. 210

    {2, 5}

    Returns: {2, 3, 5, 7 }

  6. 100000

    {2, 2, 2, 5, 5}

    Returns: {2, 2, 2, 2, 2, 5, 5, 5, 5, 5 }

  7. 32416190071

    {32416190071}

    Returns: {32416190071 }

  8. 32193520815076979

    {179424691}

    Returns: {179424691, 179426369 }

  9. 747175606

    {2}

    Returns: {2, 373587803 }

  10. 53

    {53}

    Returns: {53 }

  11. 93

    {3}

    Returns: {3, 31 }

  12. 28

    {2, 7}

    Returns: {2, 2, 7 }

  13. 66

    {2, 11}

    Returns: {2, 3, 11 }

  14. 19

    {19}

    Returns: {19 }

  15. 4077

    {3, 3}

    Returns: {3, 3, 3, 151 }

  16. 1658

    {2}

    Returns: {2, 829 }

  17. 7734

    {2, 1289}

    Returns: {2, 3, 1289 }

  18. 2510

    {2, 251}

    Returns: {2, 5, 251 }

  19. 8985

    {3, 599}

    Returns: {3, 5, 599 }

  20. 837108

    {2, 3, 3, 337}

    Returns: {2, 2, 3, 3, 3, 23, 337 }

  21. 484993

    {17, 607}

    Returns: {17, 47, 607 }

  22. 68199

    {3, 179}

    Returns: {3, 127, 179 }

  23. 586125

    {3, 5, 5}

    Returns: {3, 3, 5, 5, 5, 521 }

  24. 182120

    {2, 2, 29}

    Returns: {2, 2, 2, 5, 29, 157 }

  25. 18195326

    {2, 293473}

    Returns: {2, 31, 293473 }

  26. 19698256

    {2, 2, 1231141}

    Returns: {2, 2, 2, 2, 1231141 }

  27. 96799770

    {2, 3, 37, 709}

    Returns: {2, 3, 3, 5, 37, 41, 709 }

  28. 41616336

    {2, 2, 3}

    Returns: {2, 2, 2, 2, 3, 867007 }

  29. 62146292

    {2, 13}

    Returns: {2, 2, 13, 1195121 }

  30. 3440596343

    {2833}

    Returns: {2833, 1214471 }

  31. 7444442931

    {3, 191}

    Returns: {3, 107, 191, 121421 }

  32. 2520372976

    {2, 2, 11}

    Returns: {2, 2, 2, 2, 11, 14320301 }

  33. 5351222641

    {5351222641}

    Returns: {5351222641 }

  34. 1067500455

    {3, 7}

    Returns: {3, 5, 7, 10166671 }

  35. 68314849208

    {2, 2}

    Returns: {2, 2, 2, 8539356151 }

  36. 73849265775

    {3, 5, 281}

    Returns: {3, 3, 5, 5, 281, 1168039 }

  37. 23671554027

    {3, 31, 193}

    Returns: {3, 11, 31, 113, 193, 1061 }

  38. 483012904

    {2, 2, 5488783}

    Returns: {2, 2, 2, 11, 5488783 }

  39. 93074783711

    {7, 14107}

    Returns: {7, 13, 14107, 72503 }

  40. 145620356668

    {2, 3079}

    Returns: {2, 2, 3079, 11823673 }

  41. 627276513996

    {2, 3, 11, 59077}

    Returns: {2, 2, 3, 3, 11, 26813, 59077 }

  42. 444279237316

    {2, 111069809329}

    Returns: {2, 2, 111069809329 }

  43. 411595106454

    {2, 3, 7, 90191}

    Returns: {2, 3, 3, 3, 7, 12073, 90191 }

  44. 746365281032

    {2, 2, 44017}

    Returns: {2, 2, 2, 7, 44017, 302791 }

  45. 720720

    {2, 2, 3, 5, 11}

    Returns: {2, 2, 2, 2, 3, 3, 5, 7, 11, 13 }

  46. 665280

    {2, 2, 2, 3, 3, 7}

    Returns: {2, 2, 2, 2, 2, 2, 3, 3, 3, 5, 7, 11 }

  47. 554400

    {2, 2, 2, 3, 5, 11}

    Returns: {2, 2, 2, 2, 2, 3, 3, 5, 5, 7, 11 }

  48. 498960

    {2, 2, 3, 3, 5, 11}

    Returns: {2, 2, 2, 2, 3, 3, 3, 3, 5, 7, 11 }

  49. 332640

    {2, 2, 2, 3, 5, 11}

    Returns: {2, 2, 2, 2, 2, 3, 3, 3, 5, 7, 11 }

  50. 50400

    {2, 2, 2, 3, 5}

    Returns: {2, 2, 2, 2, 2, 3, 3, 5, 5, 7 }

  51. 576460752303423488

    {2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2}

    Returns: {2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 }

  52. 432345564227567616

    {2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2}

    Returns: {2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3 }

  53. 343937239529371488

    {2, 2, 2, 3, 7, 7, 11, 11, 13, 13, 47}

    Returns: {2, 2, 2, 2, 2, 3, 3, 7, 7, 7, 7, 7, 11, 11, 11, 11, 13, 13, 13, 47, 47 }

  54. 169096930494046152

    {2, 2, 13, 17, 17, 47, 47, 47}

    Returns: {2, 2, 2, 3, 13, 13, 17, 17, 17, 37, 47, 47, 47, 47, 47 }

  55. 1492992010450944

    {2, 2, 2, 2, 2, 2, 3, 3, 3}

    Returns: {2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 1000000007 }

  56. 231447602946796236

    {2, 3, 7, 11, 13, 47}

    Returns: {2, 2, 3, 3, 7, 7, 11, 11, 13, 17, 47, 104394737 }

  57. 1000000000000000000

    {2, 2, 2, 2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5, 5, 5, 5}

    Returns: {2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5 }

  58. 175517932966395201

    {3, 3, 7, 13, 47, 118456249}

    Returns: {3, 3, 3, 3, 7, 7, 13, 13, 47, 47, 118456249 }

  59. 33194176068608

    {2, 2, 2, 2, 2, 32416187567}

    Returns: {2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 32416187567 }

  60. 526477903055332542

    {2, 3, 3, 47, 228204732751}

    Returns: {2, 3, 3, 3, 3, 3, 47, 101, 228204732751 }

  61. 697488711251146816

    {2, 2, 2, 104394737}

    Returns: {2, 2, 2, 2, 2, 2, 104394737, 104394737 }

  62. 202082451928044253

    {47, 86027947}

    Returns: {47, 49979417, 86027947 }

  63. 470848117576706911

    {937, 32452657}

    Returns: {937, 15484279, 32452657 }

  64. 429496730910720001

    {655360001}

    Returns: {655360001, 655360001 }

  65. 37588592414461729

    {193877777}

    Returns: {193877777, 193877777 }

  66. 3651003162326508

    {2, 3}

    Returns: {2, 2, 3, 304250263527209 }

  67. 999999999999999862

    {2 }

    Returns: {2, 499999999999999931 }

  68. 980000140000004278

    {2, 700000069 }

    Returns: {2, 700000031, 700000069 }

  69. 793558824758043976

    {2, 2 }

    Returns: {2, 2, 2, 99194853094755497 }

  70. 92233292289161182

    {2 }

    Returns: {2, 46116646144580591 }

  71. 992962200242288338

    {2 }

    Returns: {2, 496481100121144169 }

  72. 999999999999999842

    {2 }

    Returns: {2, 499999999999999921 }

  73. 999999799000008694

    {2, 999999937 }

    Returns: {2, 499999931, 999999937 }

  74. 200000000000000006

    {2 }

    Returns: {2, 100000000000000003 }

  75. 100000

    {2, 2, 2, 5, 5 }

    Returns: {2, 2, 2, 2, 2, 5, 5, 5, 5, 5 }

  76. 800000000000000026

    {2 }

    Returns: {2, 400000000000000013 }

  77. 999999999999999989

    {999999999999999989 }

    Returns: {999999999999999989 }

  78. 999999999999999993

    {3 }

    Returns: {3, 333333333333333331 }

  79. 199999999999999994

    {2 }

    Returns: {2, 99999999999999997 }

  80. 210

    {2, 5 }

    Returns: {2, 3, 5, 7 }

  81. 15039996049596667

    {139 }

    Returns: {139, 108201410428753 }

  82. 200000000000000026

    {2 }

    Returns: {2, 100000000000000013 }

  83. 970833680167774470

    {2, 5 }

    Returns: {2, 3, 5, 32361122672259149 }

  84. 990151289621082074

    {2 }

    Returns: {2, 495075644810541037 }

  85. 843077835197831258

    {2 }

    Returns: {2, 421538917598915629 }

  86. 999956325678898958

    {2 }

    Returns: {2, 499978162839449479 }

  87. 999999999999999896

    {2, 2 }

    Returns: {2, 2, 2, 124999999999999987 }

  88. 349272004444904014

    {2, 1000000007 }

    Returns: {2, 174636001, 1000000007 }

  89. 999999866000004473

    {999999929 }

    Returns: {999999929, 999999937 }

  90. 980000002800000002

    {2, 700000001 }

    Returns: {2, 700000001, 700000001 }

  91. 360287964820930600

    {2, 2, 5 }

    Returns: {2, 2, 2, 5, 5, 1801439824104653 }

  92. 999999999999984986

    {2 }

    Returns: {2, 499999999999992493 }

  93. 1964903306

    {2 }

    Returns: {2, 982451653 }

  94. 200110257011432018

    {2 }

    Returns: {2, 100055128505716009 }

  95. 20000002800000098

    {2, 100000007 }

    Returns: {2, 100000007, 100000007 }

  96. 21796757741761202

    {2, 104395301 }

    Returns: {2, 104395301, 104395301 }

  97. 981168724994134051

    {981168724994134051 }

    Returns: {981168724994134051 }

  98. 2000000014

    {2 }

    Returns: {2, 1000000007 }

  99. 200218200258200302

    {2 }

    Returns: {2, 100109100129100151 }

  100. 800000000000000024

    {2, 2 }

    Returns: {2, 2, 2, 100000000000000003 }

  101. 14

    {2 }

    Returns: {2, 7 }

  102. 979999868400004418

    {2, 699999953 }

    Returns: {2, 699999953, 699999953 }

  103. 200006760057122

    {2, 10000169 }

    Returns: {2, 10000169, 10000169 }

  104. 899999999999999846

    {2 }

    Returns: {2, 449999999999999923 }

  105. 183368264792

    {2, 2 }

    Returns: {2, 2, 2, 22921033099 }

  106. 74249016090130874

    {2 }

    Returns: {2, 37124508045065437 }

  107. 854217074704302454

    {2, 653535427 }

    Returns: {2, 653535401, 653535427 }

  108. 12

    {2, 3 }

    Returns: {2, 2, 3 }

  109. 239854726664911

    {15487019 }

    Returns: {15487019, 15487469 }

  110. 36028796482093054

    {2 }

    Returns: {2, 18014398241046527 }

  111. 1999999984366

    {2 }

    Returns: {2, 999999992183 }

  112. 621378720128007854

    {2, 999000011 }

    Returns: {2, 311000357, 999000011 }

  113. 237746308477719406

    {2 }

    Returns: {2, 118873154238859703 }

  114. 999999999999999134

    {2 }

    Returns: {2, 499999999999999567 }

  115. 999999923000000882

    {2, 999999937 }

    Returns: {2, 499999993, 999999937 }

  116. 978266565744874558

    {2 }

    Returns: {2, 489133282872437279 }

  117. 320000041600000774

    {2, 400000043 }

    Returns: {2, 400000009, 400000043 }

  118. 2001300200604902

    {2, 100019 }

    Returns: {2, 100003, 100019, 100043 }

  119. 885909753408416474

    {2, 999999751 }

    Returns: {2, 442954987, 999999751 }

  120. 5720972626

    {2 }

    Returns: {2, 2860486313 }

  121. 999999951389101934

    {2, 707106791 }

    Returns: {2, 707106737, 707106791 }

  122. 7553350875370

    {2, 785839 }

    Returns: {2, 5, 785839, 961183 }

  123. 678679667760357089

    {67867967 }

    Returns: {67867967, 9999999967 }

  124. 1390710599625153

    {3, 27644437 }

    Returns: {3, 16769023, 27644437 }

  125. 64832380142

    {2 }

    Returns: {2, 32416190071 }

  126. 500000012000000054

    {2, 500000009 }

    Returns: {2, 500000003, 500000009 }

  127. 948047602067304166

    {2, 961748941 }

    Returns: {2, 492876863, 961748941 }

  128. 999999875021574338

    {2, 707106737 }

    Returns: {2, 707106737, 707106737 }

  129. 499999818000016562

    {2, 499999909 }

    Returns: {2, 499999909, 499999909 }

  130. 288230376151711718

    {2 }

    Returns: {2, 144115188075855859 }

  131. 3000000210

    {2, 5 }

    Returns: {2, 3, 5, 100000007 }

  132. 722664438997003402

    {2, 4200084451 }

    Returns: {2, 86029751, 4200084451 }

  133. 199996160018414

    {2, 9999907 }

    Returns: {2, 9999901, 9999907 }

  134. 999999747000012922

    {2, 999999929 }

    Returns: {2, 499999909, 999999929 }

  135. 8000000056

    {2, 2 }

    Returns: {2, 2, 2, 1000000007 }

  136. 734064161753028154

    {2, 982451707 }

    Returns: {2, 373587911, 982451707 }

  137. 799999999999999976

    {2, 2 }

    Returns: {2, 2, 2, 99999999999999997 }

  138. 965626188232372178

    {2, 694847533 }

    Returns: {2, 694847533, 694847533 }

  139. 937357814443548326

    {2, 694847533 }

    Returns: {2, 674506111, 694847533 }

  140. 999999874000003969

    {999999937 }

    Returns: {999999937, 999999937 }

  141. 231219114367441138

    {2, 504547 }

    Returns: {2, 227569, 504547, 1006883 }

  142. 104267587982426282

    {2 }

    Returns: {2, 52133793991213141 }

  143. 499999924000000966

    {2, 499999993 }

    Returns: {2, 499999931, 499999993 }

  144. 458885063689113602

    {2, 479001599 }

    Returns: {2, 479001599, 479001599 }

  145. 357815296795805258

    {2, 433024223 }

    Returns: {2, 413158523, 433024223 }

  146. 606197161055787754

    {2, 599144041 }

    Returns: {2, 505885997, 599144041 }

  147. 319999926400004182

    {2, 399999959 }

    Returns: {2, 399999949, 399999959 }

  148. 6000000001

    {6000000001 }

    Returns: {6000000001 }

  149. 810054180971804662

    {2, 900007 }

    Returns: {2, 500009, 900007, 900037 }

  150. 30000000210

    {2, 5 }

    Returns: {2, 3, 5, 1000000007 }

  151. 999730024299271

    {99991, 99991 }

    Returns: {99991, 99991, 99991 }

  152. 21755069872

    {2, 2, 36871 }

    Returns: {2, 2, 2, 2, 36871, 36877 }

  153. 888852222649332302

    {2, 999979 }

    Returns: {2, 444443, 999979, 999983 }

  154. 499999986000000098

    {2, 499999993 }

    Returns: {2, 499999993, 499999993 }

  155. 999999999999998146

    {2 }

    Returns: {2, 499999999999999073 }

  156. 250315132318522

    {2, 50021 }

    Returns: {2, 50021, 50021, 50021 }

  157. 799999999999999982

    {2 }

    Returns: {2, 399999999999999991 }

  158. 427651727822255162

    {2, 982451653 }

    Returns: {2, 217645177, 982451653 }

  159. 200000000138

    {2 }

    Returns: {2, 100000000069 }

  160. 80179124953718456

    {2, 2 }

    Returns: {2, 2, 2, 10022390619214807 }

  161. 16002320092400918

    {2, 200009 }

    Returns: {2, 200003, 200009, 200017 }

  162. 999999271665052798

    {2, 793699 }

    Returns: {2, 793691, 793699, 793711 }

  163. 961748949655740469

    {961748941 }

    Returns: {961748941, 1000000009 }

  164. 50419013362

    {2 }

    Returns: {2, 25209506681 }

  165. 945764098

    {2 }

    Returns: {2, 472882049 }

  166. 20000000004130766

    {2 }

    Returns: {2, 10000000002065383 }

  167. 999999999999999766

    {2 }

    Returns: {2, 499999999999999883 }

  168. 142234025442142234

    {2 }

    Returns: {2, 71117012721071117 }

  169. 25514699833688

    {2, 2, 24793 }

    Returns: {2, 2, 2, 13, 24793, 9895279 }

  170. 998254128064864128

    {2, 2, 2, 2, 701 }

    Returns: {2, 2, 2, 2, 2, 2, 2, 3, 701, 3708445257017 }

  171. 855925001274976082

    {2, 654188429 }

    Returns: {2, 654188429, 654188429 }

  172. 979999739600017298

    {2, 699999907 }

    Returns: {2, 699999907, 699999907 }

  173. 948620324694494954

    {2 }

    Returns: {2, 474310162347247477 }

  174. 777575109091711366

    {2, 852457 }

    Returns: {2, 535013, 852457, 852463 }

  175. 2000000018

    {2 }

    Returns: {2, 1000000009 }

  176. 5942430146

    {2 }

    Returns: {2, 2971215073 }

  177. 420

    {2, 3, 7 }

    Returns: {2, 2, 3, 5, 7 }

  178. 992000000000000072

    {2, 2 }

    Returns: {2, 2, 2, 124000000000000009 }

  179. 999999999999999995

    {5, 599, 369743471 }

    Returns: {5, 29, 599, 31139, 369743471 }

  180. 750000009000000027

    {3, 500000003 }

    Returns: {3, 500000003, 500000003 }

  181. 26915972537950862

    {2 }

    Returns: {2, 13457986268975431 }

  182. 23451616243765046

    {2, 227189 }

    Returns: {2, 227177, 227189, 227191 }

  183. 500000018000000162

    {2, 500000009 }

    Returns: {2, 500000009, 500000009 }

  184. 965211250482432409

    {982451653 }

    Returns: {982451653, 982451653 }

  185. 80000028800002574

    {2, 200000039 }

    Returns: {2, 200000033, 200000039 }

  186. 19999999999999874

    {2 }

    Returns: {2, 9999999999999937 }

  187. 2166010111093742

    {2, 102677 }

    Returns: {2, 102593, 102677, 102811 }

  188. 333333333333333331

    {333333333333333331 }

    Returns: {333333333333333331 }

  189. 38

    {2 }

    Returns: {2, 19 }

  190. 100000007700000049

    {100000007 }

    Returns: {100000007, 1000000007 }

  191. 32193212922307583

    {179424671 }

    Returns: {179424671, 179424673 }

  192. 90

    {2, 3 }

    Returns: {2, 3, 3, 5 }

  193. 60131588110926522

    {2, 100003, 1000033 }

    Returns: {2, 3, 100003, 100213, 1000033 }

  194. 200000000000000042

    {2 }

    Returns: {2, 100000000000000021 }

  195. 500000006000000018

    {2, 500000003 }

    Returns: {2, 500000003, 500000003 }

  196. 3430

    {2, 7, 7 }

    Returns: {2, 5, 7, 7, 7 }

  197. 10000000600000011

    {3, 3, 1163 }

    Returns: {3, 3, 3, 281, 1163, 1133313931 }

  198. 2000000000000074

    {2 }

    Returns: {2, 1000000000000037 }

  199. 12423

    {3, 101 }

    Returns: {3, 41, 101 }

  200. 2310

    {2, 5, 11 }

    Returns: {2, 3, 5, 7, 11 }

  201. 30

    {2, 5 }

    Returns: {2, 3, 5 }

  202. 999999999999999690

    {2, 5 }

    Returns: {2, 3, 5, 33333333333333323 }

  203. 719939538069374498

    {2, 599974807 }

    Returns: {2, 599974807, 599974807 }

  204. 9999996000000319

    {99999971 }

    Returns: {99999971, 99999989 }

  205. 800000023600000126

    {2, 1000000007 }

    Returns: {2, 400000009, 1000000007 }

  206. 198389706189510994

    {2 }

    Returns: {2, 99194853094755497 }

  207. 7400837602790641

    {86028121 }

    Returns: {86028121, 86028121 }

  208. 969969

    {3, 11, 17 }

    Returns: {3, 7, 11, 13, 17, 19 }

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: