Statistics

Problem Statement for "EnergySource"

Problem Statement

You have been given a single source of energy. Its initial power is power.

You can split this source of energy into multiple smaller sources. You have to do this in a series of one or more steps. In each step you can choose an existing energy source with some power P, choose a positive integer x that divides P, and split the chosen energy source into x separate new energy sources, each with power (P/x).

Given a collection of energy sources, its spread is the product of all their powers.

Find all different collections of energy sources that can be produced from the one given energy source. Let A be the number of those collections. Let B be the sum of all their spreads. Return a long[] with two elements: { A, B }.

Definition

Class:
EnergySource
Method:
countDifferentSources
Parameters:
int
Returns:
long[]
Method signature:
long[] countDifferentSources(int number)
(be sure your method is public)

Constraints

  • power will be between 1 and 90, inclusive.

Examples

  1. 3

    Returns: {2, 4 }

    There are two possible collections of energy sources: {3}: you keep the original source {1, 1, 1}: you split the original source into three smaller sources, each with power 1 The first collection has spread 3, the second collection has spread 1*1*1 = 1, thus the sum of their spreads is 3+1 = 4.

  2. 10

    Returns: {9, 103 }

    There are 9 distinct collections of energy sources that can be produced: {10}, {5, 5}, {2, 2, 2, 2, 2}, {5, 1, 1, 1, 1, 1}, {2, 2, 2, 2, 1, 1}, {2, 2, 2, 1, 1, 1, 1}, {2, 2, 1, 1, 1, 1, 1, 1}, {2, 1, 1, 1, 1, 1, 1, 1, 1} and {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}. Sum of their spreads (in the order in which we listed them) is 10+25+32+5+16+8+4+2+1=103

  3. 1

    Returns: {1, 1 }

  4. 90

    Returns: {98014, 45465390986863499 }

    This is the largest possible input (but not necessarily the largest possible output). Is your solution fast enough?

  5. 48

    Returns: {6978, 9697161469 }

  6. 2

    Returns: {2, 3 }

  7. 4

    Returns: {4, 11 }

  8. 5

    Returns: {2, 6 }

  9. 6

    Returns: {7, 33 }

  10. 7

    Returns: {2, 8 }

  11. 8

    Returns: {10, 83 }

  12. 9

    Returns: {5, 49 }

  13. 11

    Returns: {2, 12 }

  14. 12

    Returns: {34, 925 }

  15. 13

    Returns: {2, 14 }

  16. 14

    Returns: {11, 325 }

  17. 15

    Returns: {10, 534 }

  18. 16

    Returns: {36, 2899 }

  19. 17

    Returns: {2, 18 }

  20. 18

    Returns: {64, 9276 }

  21. 19

    Returns: {2, 20 }

  22. 20

    Returns: {60, 14613 }

  23. 21

    Returns: {12, 3700 }

  24. 22

    Returns: {15, 4249 }

  25. 23

    Returns: {2, 24 }

  26. 24

    Returns: {320, 306877 }

  27. 25

    Returns: {7, 3931 }

  28. 26

    Returns: {17, 16591 }

  29. 27

    Returns: {23, 43357 }

  30. 28

    Returns: {94, 261901 }

  31. 29

    Returns: {2, 30 }

  32. 30

    Returns: {297, 1519070 }

  33. 31

    Returns: {2, 32 }

  34. 32

    Returns: {202, 1738259 }

  35. 33

    Returns: {16, 267216 }

  36. 34

    Returns: {21, 262483 }

  37. 35

    Returns: {14, 117298 }

  38. 36

    Returns: {1488, 54843295 }

  39. 37

    Returns: {2, 38 }

  40. 38

    Returns: {23, 1048993 }

  41. 39

    Returns: {18, 2393902 }

  42. 40

    Returns: {776, 66410105 }

  43. 41

    Returns: {2, 42 }

  44. 42

    Returns: {610, 149163614 }

  45. 43

    Returns: {2, 44 }

  46. 44

    Returns: {186, 95720925 }

  47. 45

    Returns: {148, 57996444 }

  48. 46

    Returns: {27, 16777813 }

  49. 47

    Returns: {2, 48 }

  50. 49

    Returns: {9, 960849 }

  51. 50

    Returns: {319, 356400228 }

  52. 51

    Returns: {22, 193715514 }

  53. 52

    Returns: {244, 1793013589 }

  54. 53

    Returns: {2, 54 }

  55. 54

    Returns: {2593, 19806910791 }

  56. 55

    Returns: {18, 61212366 }

  57. 56

    Returns: {1520, 16565263301 }

  58. 57

    Returns: {24, 1743399496 }

  59. 58

    Returns: {33, 1073742751 }

  60. 59

    Returns: {2, 60 }

  61. 60

    Returns: {19303, 1140489018775 }

  62. 61

    Returns: {2, 62 }

  63. 62

    Returns: {35, 4294968349 }

  64. 63

    Returns: {219, 27070609111 }

  65. 64

    Returns: {1828, 258002514579 }

  66. 65

    Returns: {20, 1526281204 }

  67. 66

    Returns: {1848, 1371914744222 }

  68. 67

    Returns: {2, 68 }

  69. 68

    Returns: {384, 595658027061 }

  70. 69

    Returns: {28, 141214781028 }

  71. 70

    Returns: {1199, 492479454470 }

  72. 71

    Returns: {2, 72 }

  73. 72

    Returns: {85182, 167750707863709 }

  74. 73

    Returns: {2, 74 }

  75. 74

    Returns: {41, 274877908423 }

  76. 75

    Returns: {445, 3044128555559 }

  77. 76

    Returns: {466, 10629050859325 }

  78. 77

    Returns: {20, 2328317164 }

  79. 78

    Returns: {2869, 123513841414334 }

  80. 79

    Returns: {2, 80 }

  81. 80

    Returns: {23932, 308402834038049 }

  82. 81

    Returns: {239, 17180634420931 }

  83. 82

    Returns: {45, 4398046512907 }

  84. 83

    Returns: {2, 84 }

  85. 84

    Returns: {62194, 9863652920374919 }

  86. 85

    Returns: {24, 953675825088 }

  87. 86

    Returns: {47, 17592186046393 }

  88. 87

    Returns: {34, 102945566072670 }

  89. 88

    Returns: {4128, 1464499661936717 }

  90. 89

    Returns: {2, 90 }

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: