Statistics

Problem Statement for "LCMGCD"

Problem Statement

You are given the int[] x: a list containing n integers. Each element of x is a positive integer of the form 2^a * 3^b, where a and b are some nonnegative integers. The elements of x are not necessarily distinct.

You are going to perform n-1 operations. Each operation will consist of the following steps:

  1. Choose two distinct indices into your list. Let X and Y be the numbers at those indices. Remove both of them from the list. (Note that X and Y are allowed to have the same value.)
  2. Compute one of two possible values: either the greatest common divisor (gcd) of X and Y, or the least common multiple (lcm) of X and Y.
  3. Append the computed value to your list.
Obviously, after n-1 operations you will be left with a single integer.

In addition to x you are given the int t. You would like to know whether it is possible to perform the sequence of operations on x in such a way that the final integer will be t. If it is possible, return "Possible", otherwise return "Impossible".

Definition

Class:
LCMGCD
Method:
isPossible
Parameters:
int[], int
Returns:
String
Method signature:
String isPossible(int[] x, int t)
(be sure your method is public)

Constraints

  • x will contain between 1 and 50 elements, inclusive.
  • Each element of x will be between 1 and 10^9, inclusive.
  • t will be between 1 and 10^9, inclusive.
  • t and each element of x will be of the form 2^i*3^j for some nonnegative i,j.

Examples

  1. {2,3}

    6

    Returns: "Possible"

    We can take the lcm to reach the goal.

  2. {4,9}

    6

    Returns: "Impossible"

    We have lcm(4,9) = 36 and gcd(4,9) = 1. It's impossible to get 6.

  3. {6,12,24,18,36,72,54,108,216}

    36

    Returns: "Possible"

  4. {6,27,81,729}

    6

    Returns: "Impossible"

  5. {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    1

    Returns: "Possible"

  6. {72,16,16,16,16,16,27,27,27,27,27,27,27,27,27}

    72

    Returns: "Possible"

  7. {100663296, 544195584, 229582512, 59049}

    60466176

    Returns: "Possible"

    Watch out for integer overflow. The intermediate results won't always fit into a 32-bit integer variable.

  8. {648,864,18}

    72

    Returns: "Impossible"

    (2^3*3^4,2^5*3^3,2^1*3^2), 2^3*3^2

  9. {1}

    1

    Returns: "Possible"

  10. {6}

    3

    Returns: "Impossible"

  11. {6,27,81,729,6}

    6

    Returns: "Possible"

  12. {36,81,16,54,24}

    36

    Returns: "Possible"

  13. {18,3,4}

    6

    Returns: "Possible"

  14. {12,2,9}

    6

    Returns: "Possible"

  15. {12,12,18,18,18,18,27,9,54}

    12

    Returns: "Possible"

  16. {1,2,4,12,36,8,24,48,16}

    6

    Returns: "Impossible"

  17. {6,27}

    6

    Returns: "Impossible"

  18. {6,27,27}

    6

    Returns: "Impossible"

  19. {6,6,27}

    6

    Returns: "Possible"

  20. {6,6,27,27}

    6

    Returns: "Possible"

  21. {4,16,472392,39366,1,497664,648,27,16,20736,432,144,486,648,648,10368,432,708588,52488,1,69984,162,162,20736,432,432,7776,48,324,216,48,48,5038848,54,6,40310784,26244,165888,54,1259712,36,16,45349632,648,1417176,162,139968,2592,54,22674816}

    1296

    Returns: "Possible"

  22. {2187,54,18,2187,54,59049,2,729,19683,6,18,729,2,59049,2,6,2,177147,54,6561,18,2,2187,6561,18,2,729,19683,177147,729,54,54,54,6,19683,2187,729,6561,54,2,243,2187,2,177147,54,54,59049,2187,59049,6}

    162

    Returns: "Impossible"

  23. {1944,729,16,11943936,2048,72,2048,3,41472,324,373248,1492992,3888,23328,73728,864,2985984,2916,186624,2916,11943936,2592,11664,46656,5832,1728,55296,746496,5971968,3,1458,32,486,2985984,165888,1536,486,24,2916,13824,46656,373248,9,27648,1492992,48,373248,1728,1458,124416}

    93312

    Returns: "Impossible"

  24. {1296,729,12754584,16,16,7776,5832,708588,864,16,48,59049,165888,59049,118098,3888,864,1296,3188646,3888,3888,16,3888,432,1296,5832,1458,128,7776,1024,157464,432,55296,1458,17496,729,1296,16,5832,128,96,19683,52488,59049,497664,59049,3888,3888,1062882,432}

    11664

    Returns: "Possible"

  25. {12,118098,6561,4608,81,162,9,486,2,81,81,1536,13824,162,4,354294,729,9,2304,2,4374,864,2,36,12,118098,162,108,162,36,27,108,1,6561,864,4608,243,162,54,288,96,59049,6,12,162,36,2187,36,243,4}

    324

    Returns: "Possible"

  26. {2592,3779136,1259712,5184,1259712,5184,162,81,1024,18432,6912,512,15552,1296,5184,3072,46656,5184,5184,11337408,5184,15552,12288,55296,5184,5184,419904,11337408,1152,3779136,1296,81,5184,139968,5184,5184,768,5184,73728,221184,162,2592,6912,24576,3779136,648,1024,81,5184,12288}

    5184

    Returns: "Possible"

  27. {54,54,27,3,3,27,27,384,384,96,27,27,1,1,9,3,4,32,54,128,2,54,54,54,27,27,18,1,18,27,27,27,6,1,54,2,8,54,54,72,9,6,2,27,96,54,2,12,54,18}

    54

    Returns: "Possible"

  28. {576,64,6144,15552,6,576,2304,6,12,10368,64,48,576,48,5184,12288,64,384,1024,576,1259712,576,1024,20736,139968,64,576,192,36864,15552,64,16,64,15552,576,9216,384,12288,192,17915904,139968,64,768,576,73728,64,12288,64,18432,64}

    576

    Returns: "Possible"

  29. {78732,243,13122,729,13122,4782969,39366,1594323,162,18,39366,39366,3779136,559872,6,17496,354294,162,2,19683,531441,162,81,729,19683,486,45349632,139968,13122,102036672,531441,1062882,944784,6377292,1,13122,629856,18,9,139968,419904,1458,486,6,27,6561,19683,6561,96,1062882}

    4374

    Returns: "Possible"

  30. {139968,81,8,24,82944,486,559872,4,24,1944,144,2239488,8,24,1944,576,54,9,2,27648,279936,8,24,216,729,16,972,72,139968,279936,559872,768,128,243,288,6,1119744,11664,1944,139968,9,34992,124416,36,69984,1119744,31104,216,139968,5832}

    17496

    Returns: "Impossible"

  31. {7776,314928,288,69984,209952,864,76527504,69984,5668704,153055008,4478976,69984,96,69984,1889568,864,708588,559872,7776,472392,629856,1889568,2125764,5668704,104976,51018336,139968,2239488,8503056,5668704,2239488,1062882,944784,708588,559872,139968,8503056,4478976,4478976,51018336,26244,1889568,153055008,288,69984,23328,209952,209952,1119744,69984}

    69984

    Returns: "Possible"

  32. {3,6,4,9,4,4,3,4,3,6,6561,4,4,6,4,6,3,4,6,4,4374,3,1458,3,6,4,243,4,4,4,4,1458,3,13122,6,1458,3,4,4,4,4,4,4,27,1458,4,4374,4,4,162}

    12

    Returns: "Possible"

  33. {27,9565938,5668704,9565938,81,204073344,314928,4374,39366,4374,76527504,354294,1062882,729,1062882,4374,4374,729,1,4374,27,4374,153055008,102036672,4374,354294,4374,118098,4374,4374,27,1,4374,4374,118098,1,81,27,5668704,13122,944784,45349632,1679616,4374,4251528,9565938,209952,4374,118098,4374}

    4374

    Returns: "Possible"

  34. {10368,10077696,1296,512,18432,3072,45349632,2,10368,2239488,18432,165888,18,216,1296,72,768,41472,1296,5184,181398528,1679616,124416,3456,5184,1296,216,1119744,1296,165888,8,2048,1296,7776,2592,18432,1296,22674816,24,9,13436928,27,839808,45349632,373248,2239488,1,256,36,2592}

    1296

    Returns: "Possible"

  35. {373248,36,36,48,746496,23328,746496,144,144,36,373248,1728,16,48,18,3456,144,144,144,48,16,72,144,144,18,144,93312,4478976,72,144,144,144,48,18,144,16,48,144,144,16,1679616,16,144,18,72,18,72,279936,144,124416}

    144

    Returns: "Possible"

  36. {54,139968,306110016,324,6,139968,2239488,139968,118098,279936,110592,4478976,139968,306110016,2985984,139968,157464,1417176,216,11337408,104976,1458,24,419904,11337408,11337408,76527504,139968,139968,3779136,1296,139968,559872,11337408,26244,139968,139968,82944,1119744,11337408,11337408,19131876,139968,419904,1259712,26244,139968,23328,139968,139968}

    139968

    Returns: "Possible"

  37. {17496,32,39366,17496,17496,9565938,192,2187,1062882,17496,17496,354294,2187,17496,8748,384,26244,373248,2187,1062882,19131876,17496,96,8748,177147,8748,384,354294,531441,768,2187,17496,11664,16,4374,19683,7776,1296,17496,32,8748,6912,864,7776,2592,2187,6377292,17496,17496,48}

    17496

    Returns: "Possible"

  38. {248832,82944,3456,2048,4374,139968,19131876,559872,59049,17496,8748,13122,279936,256,288,1417176,4251528,2048,26244,9216,4478976,7776,236196,354294,3072,3456,26244,1492992,2304,17496,512,62208,19131876,1417176,20736,26244,4478976,9565938,8748,17496,9216,19131876,236196,4374,69984,2187,2187,1119744,6912,1594323}

    34992

    Returns: "Impossible"

  39. {3359232,1536,48,1536,46656,384,1728,48,48,48,48,48,96,3359232,15552,3072,48,209952,82944,48,27648,384,62208,48,6912,48,1536,48,559872,48,139968,209952,93312,4608,1536,46656,48,48,48,23328,7776,165888,4478976,48,48,6912,3072,48,48,48}

    48

    Returns: "Possible"

  40. {8503056,3888,8503056,3888,34992,25509168,8503056,314928,104976,25509168,8503056,944784,432,5184,768,25509168,144,314928,8503056,144,16,432,8503056,8503056,944784,314928,48,104976,8503056,3888,8503056,432,1296,104976,8503056,2592,6912,314928,256,3888,768,248832,16,25509168,432,314928,2592,144,165888,944784}

    11664

    Returns: "Impossible"

  41. {384,128,419904,3,32,2,48,34992,32,32,864,23328,1,162,2592,1,4096,2048,36864,2,864,16,1024,2048,512,4,1024,768,1,512,16,128,4,2,48,839808,256,46656,55296,4,32,128,746496,82944,23328,192,768,4,2592,4}

    96

    Returns: "Possible"

  42. {512,192,192,864,4608,96,288,864,157464,864,36864,288,576,944784,96,104976,256,96,288,1152,972,192,512,864,314928,864,864,2304,864,576,4608,864,864,288,288,96,864,26244,2048,236196,96,576,1024,1024,864,32,864,512,32,96}

    864

    Returns: "Possible"

  43. {157464,11664,93312,93312,373248,314928,93312,204073344,746496,11664,11337408,4251528,3779136,17496,11337408,186624,93312,816293376,46656,34012224,1417176,46656,419904,46656,17496,186624,6718464,746496,17496,8503056,11664,7558272,23328,11664,10077696,46656,204073344,69984,12754584,30233088,419904,139968,17496,11337408,1417176,93312,2519424,472392,373248,5668704}

    5832

    Returns: "Possible"

  44. {1679616,324,324,2592,839808,1296,2592,1679616,3779136,2592,2592,81,362797056,2592,2592,2592,2592,2592,162,241864704,81,4478976,2592,162,2592,162,40310784,80621568,2592,324,162,11337408,2592,2519424,22674816,2592,2592,2592,2592,1296,1119744,62208,324,2592,995328,186624,2592,60466176,124416,26873856}

    2592

    Returns: "Possible"

  45. {2,3888,648,1,2,2,26244,2,2,17496,1,104976,2,2,1,1,1,2,186624,2,104976,2,2,209952,2,2,1296,1,15552,216,2,1,2,2,1,576,2,2,2,1,31104,2,2,2,20736,2,2,1,648,1}

    6

    Returns: "Impossible"

  46. {27,82944,2592,279936,1,324,2592,90699264,81,8748,1889568,120932352,5038848,384,78732,39366,69984,82944,1,2592,16,6,64,9216,81,69984,3072,26244,81,31104,64,2592,162,2304,1119744,177147,1296,324,59049,324,486,2592,324,157464,108,23328,80621568,10368,2592,629856}

    2592

    Returns: "Possible"

  47. {72,12754584,72,52488,72,2592,24,1594323,248832,3188646,144,59049,59049,82944,5184,13122,38263752,648,216,3188646,6377292,8,78732,78732,7776,72,864,5832,1024,2125764,384,124416,72,5832,72,1944,472392,26244,19131876,32,78732,354294,216,52488,2125764,1944,746496,4251528,648,118098}

    17496

    Returns: "Impossible"

  48. {118098,54,54,486,4374,13122,4374,39366,162,486,162,54,4374,54,39366,54,54,54,162,54,4374,162,1458,1458,54,54,54,54,54,4374,4374,1458,54,118098,13122,54,486,54,54,54,4374,54,118098,1458,118098,54,162,54,4374,54}

    54

    Returns: "Possible"

  49. {248832,2592,629856,972,27,27,7776,15116544,248832,3888,4,1,1944,288,7776,3888,5668704,2592,288,34012224,7776,96,629856,3359232,13436928,486,15552,96,243,995328,139968,36,3,3888,12,864,186624,68024448,2592,243,5668704,7776,497664,32,31104,288,7776,1679616,72,209952}

    7776

    Returns: "Possible"

  50. {648,26244,8748,216,512,93312,177147,729,944784,3888,8,118098,2916,729,3072,648,8,48,59049,144,96,648,288,24,729,648,1152,3888,192,209952,216,3779136,24,1119744,2916,512,128,216,24,648,8,648,648,72,2187,6561,768,216,128,864}

    648

    Returns: "Possible"

  51. {2916,1296,31104,2916,1944,46656,2916,46656,3456,23328,864,2916,192,93312,2916,2916,864,2916,2916,64,3888,2916,46656,15552,62208,2916,93312,186624,373248,2916,11664,2916,144,512,373248,93312,23328,11664,648,2916,216,512,15552,2916,2916,11664,1536,23328,384,216}

    2916

    Returns: "Possible"

  52. {1,2125764,5832,54,3,486,54,2916,27,162,1,3,209952,26244,54,2,3,23328,486,1889568,93312,157464,6,629856,3,68024448,11337408,81,1,27,6,5832,27,3,2,11664,54,11664,9,11664,4251528,81,2916,243,18,93312,78732,9,5832,243}

    1458

    Returns: "Impossible"

  53. {49152,3,2239488,3,1024,279936,18,18432,512,12,4096,49152,8,4096,6144,221184,24,107495424,69984,512,27,3072,1536,1152,3456,12288,31104,2,8,8192,864,35831808,4,2592,3456,2048,256,96,31104,48,419904,147456,4608,192,1152,10368,12,12,2916,3456}

    384

    Returns: "Possible"

  54. {2,3,18,2,27,27,18,2,62208,54,39366,6,54,27,54,93312,162,162,39366,59049,6561,9,1,1259712,9,19683,104976,118098,2916,944784,3,20736,54,18,729,1,78732,1,18,18,10368,27,9,54,54,1,9,39366,59049,54}

    54

    Returns: "Possible"

  55. {1458,2304,1,279936,279936,34992,10368,128,32,4,1,1,1,13122,62208,1152,4,1458,139968,52488,4,3456,1,864,32,3456,1,128,1,256,1,1,576,18,5832,15552,1,1,839808,64,11664,1,279936,7776,31104,54,8,1,128,128}

    6

    Returns: "Impossible"

  56. {432,2592,124416,288,15552,248832,124416,8957952,2592,139968,559872,8,108,2239488,2592,2592,108,18,2592,995328,32,2592,108,9,216,2592,3,2592,96,288,241864704,1679616,2592,2,2519424,5038848,32,72,279936,2592,864,48,2592,24,6,16,2592,62208,2592,96}

    2592

    Returns: "Possible"

  57. {576,1728,3359232,139968,192,1728,82944,3359232,165888,1728,576,1728,1728,1728,1728,124416,80621568,3,64,15552,6,26873856,64,5184,576,1728,1728,46656,96,4478976,1728,576,82944,24,15552,144,16,1259712,2239488,663552,4,1728,419904,1728,139968,16,1259712,288,48,1728}

    1728

    Returns: "Possible"

  58. {279936,279936,279936,612220032,124416,279936,279936,612220032,768,204073344,22674816,279936,279936,62208,279936,2519424,279936,279936,279936,1327104,7558272,279936,612220032,27648,2519424,663552,49152,279936,68024448,279936,2519424,18432,22674816,279936,68024448,279936,279936,612220032,5971968,279936,1327104,147456,279936,4096,279936,6912,612220032,7558272,279936,279936}

    279936

    Returns: "Possible"

  59. {1,157464,12754584,559872,139968,59049,69984,1062882,559872,108,139968,4782969,78732,729,8,216,729,8,34992,1,72,27,2,24,2916,139968,9,5832,38263752,972,559872,972,729,648,162,12,12,38263752,139968,59049,648,38263752,19683,6377292,157464,19683,157464,486,34992,12}

    17496

    Returns: "Possible"

  60. {139968,2592,2519424,1296,648,7558272,2592,2592,2592,2592,2592,162,1492992,1259712,2592,4478976,2592,1296,2592,81,22674816,2592,3359232,162,2592,162,373248,1259712,839808,162,2592,2592,648,324,81,2592,186624,648,2592,2592,162,62208,324,648,2592,186624,2592,2592,81,2592}

    2592

    Returns: "Possible"

  61. {648,6561,1024,96,279936,5832,16,192,13122,5832,54,768,972,26244,1024,5832,32,69984,17496,209952,4608,384,26244,256,52488,27,32,9,2187,72,192,384,46656,108,17496,11664,864,108,4374,288,6718464,559872,17496,64,7776,6718464,1944,54,648,243}

    24

    Returns: "Possible"

  62. {13824,2519424,20155392,20736,1492992,629856,93312,4478976,5038848,1119744,373248,746496,13824,2519424,20155392,497664,1259712,2519424,1728,248832,124416,629856,23328,4478976,3359232,746496,13824,46656,10077696,279936,10077696,559872,2519424,139968,82944,839808,13824,46656,2239488,82944,7776,82944,3456,13436928,55296,13436928,31104,559872,23328,27648}

    144

    Returns: "Impossible"

  63. {7776,11664,288,144,72,24,4,48,7776,2187,16,288,8,24,7776,24,288,8748,629856,6144,144,768,18,629856,384,9,144,9,12288,1,288,209952,108,6561,1458,72,7776,288,2187,629856,288,4,2916,288,1,18,288,23328,69984,1}

    288

    Returns: "Possible"

  64. {3,3072,52488,8,81,1536,3072,12,768,6,8,209952,8,24,486,192,3,6,24,746496,3,8,1119744,1458,648,1944,216,3,139968,6,12,52488,186624,1944,48,8,1296,3456,162,1536,52488,486,288,24,8,24,5832,18,52488,17496}

    24

    Returns: "Possible"

  65. {2304,6912,54,54,6912,864,54,108,2304,108,864,432,512,6912,13824,864,1536,2304,3456,6912,48,864,48,1728,108,4608,864,2304,27,432,384,54,13824,864,288,27,432,27648,54,576,288,27,576,27,576,192,3072,144,96,3456}

    216

    Returns: "Impossible"

  66. {486,243,1944,243,3888,3888,3888,3888,243,3888,3888,4,3888,1944,486,216,9,6,243,3888,12,162,108,3888,4,4,1944,3888,6,243,243,9,1,3888,243,3888,486,3888,243,486,243,3888,81,3888,3888,1944,3888,3888,216,1944}

    3888

    Returns: "Possible"

  67. {2,36,11664,186624,472392,36,27,3,1417176,2187,23328,354294,12754584,46656,1,12754584,11664,39366,26244,472392,12754584,36,11664,59049,472392,972,4,6561,78732,472392,4251528,6,186624,23328,1062882,59049,93312,746496,11664,708588,746496,12754584,746496,18,972,39366,46656,1594323,81,52488}

    5832

    Returns: "Possible"

  68. {16,7776,64,16,128,48,384,16,128,384,4,1,147456,24,4,384,384,12,4,52488,64,4,12,27648,1296,128,16,432,128,2,6,128,3981312,243,1,48,24,2,54,6912,3,52488,128,1458,384,384,128,384,1,24}

    384

    Returns: "Possible"

  69. {1944,19683,27,2,2187,18,81,354294,2187,39366,354294,19683,2187,59049,18,3,4374,13122,59049,19683,177147,2187,3888,1458,81,27,2,7776,54,27,972,162,1458,18,6561,15552,54,1,15552,2187,18,972,27,81,59049,15552,177147,9,15552,9}

    486

    Returns: "Possible"

  70. {139968,34992,64,139968,139968,4782969,19131876,139968,139968,139968,17496,139968,12754584,34992,531441,139968,2834352,64,139968,139968,64,1417176,139968,3188646,38263752,139968,17496,192,69984,2187,139968,139968,139968,5668704,139968,46656,15552,78732,1062882,153055008,2187,69984,139968,64,157464,8748,5184,139968,8748,5184}

    139968

    Returns: "Possible"

  71. {9216,18432,18432,18432,6912,41472,1152,165888,128,128,81,384,1152,384,128,1152,442368,373248,162,1152,73728,5971968,1152,1152,1152,17496,384,161243136,1152,6912,384,128,559872,384,1152,108,128,8748,1152,36864,2592,5184,9216,147456,1152,108,128,128,2916,147456}

    1152

    Returns: "Possible"

  72. {1458,9,81,1458,216,10368,1458,1062882,3456,1458,118098,1594323,2187,19683,1296,1458,10368,354294,81,9,324,531441,186624,729,729,6561,23328,1458,177147,4374,93312,177147,729,729,1458,4374,729,729,288,1458,118098,48,432,1458,1458,23328,19683,19683,96,16}

    1458

    Returns: "Possible"

  73. {18,59049,2,6561,2,729,59049,19683,2,2,6,2187,2,729,2187,6,18,18,6,2187,81,81,2187,243,6,6,6,6,729,81,19683,243,19683,18,6,2,729,243,59049,59049,18,19683,59049,243,6,81,2,59049,18,6561}

    54

    Returns: "Impossible"

  74. {54,54,5832,2304,54,27,1594323,1062882,1944,31104,3072,5832,9,5832,1,2916,6377292,5832,708588,648,4608,1152,1944,3,93312,8,128,3188646,256,46656,729,5832,708588,5832,186624,24,531441,216,373248,216,62208,46656,729,23328,729,82944,486,746496,729,24}

    5832

    Returns: "Possible"

  75. {6144,1152,1492992,93312,93312,192,3072,32,9216,24576,2,384,3072,20736,16,8,384,24,663552,384,48,53747712,12288,48,24,96,128,48,6144,9216,32,279936,384,8,3,128,147456,49152,279936,1536,1119744,1,128,64,384,96,2,128,128,192}

    384

    Returns: "Possible"

  76. {3072,972,64,64,64,64,24,13824,864,20736,72,729,16,12288,221184,12,12288,1,64,64,64,6144,24576,663552,3072,331776,54,64,1990656,5832,972,729,64,64,4,768,768,1119744,6144,64,768,32,48,1536,5971968,18,52488,2239488,2304,24}

    192

    Returns: "Possible"

  77. {46656,26873856,2,7558272,1944,3779136,486,4096,192,46656,20155392,3456,13824,46656,162,62208,1119744,2916,192,18,110592,2916,46656,46656,102036672,53747712,16,139968,4096,24576,5832,1458,11337408,729,46656,16,11337408,1259712,46656,53747712,3072,1944,46656,576,82944,243,73728,27,54,241864704}

    46656

    Returns: "Possible"

  78. {12,1,1536,12,1536,6144,512,192,2239488,768,1,4096,4,442368,3,53747712,27648,3,48,17915904,24576,48,32,995328,26873856,331776,1536,3981312,55296,64,24,12288,1327104,27648,331776,4,13824,995328,165888,12288,322486272,16384,2048,32,24,322486272,663552,32,26873856,32}

    1152

    Returns: "Impossible"

  79. {162,162,972,27,27,9,5668704,1,27,162,3,9,3,17496,162,162,162,162,9,3,944784,162,1,162,162,62208,209952,162,27,157464,162,162,17496,104976,9,9,9,3,3,162,3,162,162,11337408,3,1,162,162,708588,162}

    162

    Returns: "Possible"

  80. {2916,2304,18,10368,5038848,27,69984,11337408,9,5184,5668704,3,1,5184,3,18,5184,2592,3,1,5668704,9,6,5184,24,10368,6,22674816,324,1,1296,3779136,10368,3,27,2592,3,324,9,144,4,3,432,3,1,54,432,18,6,22674816}

    162

    Returns: "Impossible"

  81. {1944,8,243,2,746496,3,23328,72,324,36,746496,192,124416,2,3072,746496,186624,972,512,746496,24,36,46656,486,8,1944,216,24,186624,216,1728,8,93312,8,4608,23328,13824,32,648,3072,9216,93312,324,27,1728,6,72,8,32,46656}

    5832

    Returns: "Impossible"

  82. {512,2,128,6,4,1,12,6,12,16,1024,12,4,16,1024,1,1024,512,6,3,12,12,4,4,16,4,4,3,1,4,256,6,64,1,12,2,6,3,3,2,32,32,32,12,3,6,4,32,6,128}

    24

    Returns: "Impossible"

  83. {192,11664,11337408,46656,46656,15552,34012224,46656,5184,5184,102036672,192,708588,46656,5184,11337408,4251528,46656,3779136,8748,64,192,3779136,729,4374,1728,46656,34992,46656,4374,1458,46656,1458,6561,2834352,192,46656,46656,46656,209952,236196,34012224,64,64,46656,2187,46656,1458,46656,2834352}

    46656

    Returns: "Possible"

  84. {2,27,162,54,162,2,162,18,162,27,3,162,27,3,4374,13122,3,4374,118098,54,162,6,162,6,162,3,1,1,54,3,54,4374,3,27,18,3,118098,162,354294,118098,27,2,39366,3,27,18,3,6,54,162}

    162

    Returns: "Possible"

  85. {3888,279936,1458,4,2187,139968,4374,128,12,1062882,34992,118098,972,13824,162,59049,531441,2,54,36,12,19683,972,81,3188646,177147,559872,864,118098,1119744,3188646,39366,9,768,11664,177147,972,124416,324,10368,2,1728,17496,192,4,4374,9,108,4,108}

    8748

    Returns: "Possible"

  86. {708588,324,108,729,4,236196,36,236196,324,1458,729,12,12,12,8748,2125764,4,729,729,108,708588,1458,972,708588,1458,729,729,4,4,729,1458,8748,324,8748,36,324,8748,729,26244,729,729,26244,1458,2125764,108,2125764,324,12,729,1458}

    2916

    Returns: "Possible"

  87. {72,78732,162,324,24,4374,96,11337408,1296,82944,165888,177147,288,27,2239488,864,23328,241864704,5184,236196,3359232,288,72,1,162,54,4,5668704,144,10368,432,24,5668704,486,648,288,1679616,165888,216,864,7776,34992,82944,10368,40310784,52488,165888,32,186624,82944}

    2592

    Returns: "Possible"

  88. {162,648,1259712,27,82944,864,864,7558272,864,13436928,864,34992,864,120932352,216,60466176,864,52488,497664,69984,373248,864,40310784,13436928,81,629856,486,209952,864,864,864,11664,69984,331776,139968,373248,1458,3779136,17496,26244,324,81,216,31104,216,62208,995328,864,17496,69984}

    864

    Returns: "Possible"

  89. {4096,20736,36864,2304,839808,576,384,36,576,9,576,248832,72,18,73728,512,995328,1990656,576,72,161243136,384,9216,72,13436928,576,497664,18432,73728,24576,576,288,18432,82944,576,186624,9216,3359232,1536,73728,576,279936,82944,768,1152,384,6144,1679616,36864,9}

    576

    Returns: "Possible"

  90. {96,1152,576,128,16,839808,1152,24,279936,1152,279936,9,839808,18,128,2519424,839808,8,1152,1152,576,9,128,1152,384,288,384,279936,384,279936,48,31104,384,2519424,384,384,1152,128,3456,128,576,384,1152,1152,288,72,128,384,384,1152}

    1152

    Returns: "Possible"

  91. {27,486,24,3,512,512,162,972,24,32,32,256,3,24,256,6,3,24,8748,12,6,6,3,12,16,6561,9,12,24,6,972,24,6561,24,1024,6,27,3,13122,3,512,13122,32,32,6,36,512,12,24,24}

    24

    Returns: "Possible"

  92. {96,16,82944,324,55296,331776,1536,1728,10368,10368,5184,10368,768,1296,20736,64,36,648,10368,82944,331776,512,10368,10368,1296,768,1327104,72,2592,10368,663552,216,5184,8,4096,2304,331776,20736,648,864,331776,648,165888,20736,10368,165888,1296,5184,49152,24576}

    10368

    Returns: "Possible"

  93. {1,768,6,768,6,192,7776,3,1,36,46656,864,6,3,108,6,6,1,48,3,3,3,6,6,6,1,11664,3,46656,96,6,192,1,10368,3,6,3,6,6,6,3,6,48,6,1,1,6,10368,6,3}

    6

    Returns: "Possible"

  94. {1152,36,1152,1152,78732,26244,41472,1152,15552,559872,1152,9,34992,36,1152,4374,5184,2985984,72,1152,72,576,995328,1152,8957952,288,7776,144,72,107495424,288,1327104,36,2985984,1152,15552,27648,162,1152,36,144,72,2239488,54,1152,1152,1152,1296,5832,1152}

    1152

    Returns: "Possible"

  95. {162,324,354294,177147,15552,81,1679616,324,486,708588,162,4374,181398528,81,162,69984,6561,124416,2239488,30233088,972,162,15116544,243,162,26244,45349632,81,23328,59049,162,324,81,243,11337408,2916,162,81,324,324,419904,1458,6718464,26244,181398528,6561,729,11664,729,181398528}

    648

    Returns: "Impossible"

  96. {3,324,108,9,18,144,972,243,324,18,78732,1152,6,26244,36,4608,576,4374,144,72,18,2187,108,9,972,144,288,972,36,36,36,144,36,9,1,18,36,36,36,576,78732,36,2,78732,9,36,2,2,6561,26244}

    36

    Returns: "Possible"

  97. {729,177147,1,93312,216,354294,93312,13122,8,746496,6377292,36,746496,648,746496,2916,26244,729,1944,2125764,36,93312,72,72,2916,1458,6377292,373248,1944,729,3,729,1458,243,729,2125764,11664,729,8,4374,1944,8748,8748,8,1458,373248,216,729,8,216}

    5832

    Returns: "Possible"

  98. {46656,186624,324,5832,354294,729,5832,5832,23328,486,2916,19683,5832,746496,24,186624,12754584,1458,216,108,1,46656,3779136,8,23328,2916,5832,2834352,51018336,5832,1062882,8,486,24,729,9,12754584,972,24,373248,629856,729,729,1679616,72,24,472392,3,52488,2125764}

    5832

    Returns: "Possible"

  99. {162,72,5184,432,27,11664,104976,3072,6144,18,192,324,20736,6912,2834352,11664,2834352,432,2,314928,944784,41472,16,432,162,11664,82944,20736,2592,314928,162,2834352,34992,1536,314928,8503056,144,24,8,34992,1296,11664,104976,16,48,16,1296,2834352,11664,2834352}

    3888

    Returns: "Impossible"

  100. {192,288,768,12288,4096,24576,17496,192,2916,648,3072,192,512,192,24576,6144,2048,6144,4096,4096,17496,768,1536,36,216,6144,8192,192,23328,192,192,7776,104976,192,8192,6144,128,6144,12288,6144,2048,144,192,512,1944,1536,128,8192,128,2048}

    192

    Returns: "Possible"

  101. {96,2592,2592,23328,1062882,23328,2592,23328,19683,32,78732,23328,23328,354294,472392,864,2592,26244,32,23328,7776,288,23328,23328,23328,23328,157464,472392,864,1417176,7776,7776,8748,288,78732,12754584,96,23328,4251528,23328,23328,23328,32,118098,1062882,6377292,7776,7776,25509168,708588}

    23328

    Returns: "Possible"

  102. {629856,288,486,486,7776,216,192,192,576,48,64,192,7776,576,1728,1944,64,1728,4251528,27,236196,576,576,157464,1944,648,4,2,64,576,8,34992,144,1944,1889568,157464,576,5184,108,64,243,17006112,9,69984,288,64,192,192,354294,576}

    15552

    Returns: "Possible"

  103. {6912,36,2187,324,972,36,2916,5832,243,15552,3,324,324,243,36,1728,8748,13122,36,486,13122,3456,6,69984,52488,34992,36,3,36,972,559872,139968,1,2916,81,13122,2916,108,559872,1,864,19683,26244,3,54,1728,46656,108,36,36}

    36

    Returns: "Possible"

  104. {23328,46656,3072,46656,729,46656,46656,729,41472,5832,72,23328,8,1458,5832,2916,1458,46656,512,46656,243,256,46656,1458,72,128,46656,1458,82944,46656,46656,3456,1458,216,248832,1990656,46656,46656,4096,23328,13824,46656,2916,31104,1152,11664,46656,20736,162,46656}

    46656

    Returns: "Possible"

  105. {69984,5668704,8957952,69984,23328,1119744,1119744,69984,69984,209952,38263752,5668704,1119744,69984,139968,139968,69984,69984,69984,69984,1119744,69984,25509168,69984,5668704,2239488,139968,279936,5668704,2592,69984,1889568,864,7776,69984,314928,1417176,2125764,3188646,8503056,1889568,23328,1119744,104976,2125764,4478976,629856,157464,153055008,629856}

    69984

    Returns: "Possible"

  106. {72,5832,72,12,93312,4374,6,8,8,72,72,2,162,1,6912,576,8,24,34992,648,1728,1152,216,24,1944,2519424,288,3,72,12,12,72,648,20736,243,52488,5832,144,162,648,3,3,24,4374,24,139968,24,78732,2592,24}

    72

    Returns: "Possible"

  107. {944784,16,48,2916,1296,144,3,2834352,18,1296,27,13122,972,16,118098,2834352,4374,16,1296,3888,1296,48,16,9,72,1296,19683,6561,48,16,18,19683,104976,944784,1296,18,59049,118098,8748,72,314928,3,59049,2187,34992,2916,243,1,2,1417176}

    1296

    Returns: "Possible"

  108. {2,3,192,384,6,6,6,6,1,3,2,96,48,3,2,2,1,2,1,768,1,2,6,6,6,2,768,3,2,2,96,2,6,768,96,1,3,6,2,96,2,48,6,48,2,3,6,1,24,768}

    12

    Returns: "Impossible"

  109. {12,2,18,3,8748,1152,72,9,1152,12,1,2916,3,4,18,6,108,4,486,18,12,4608,3,486,1458,2187,144,12,4,18,576,18,9,6,4,18,3,26244,2,1,12,12,3,4374,4,18,9,2,26244,18}

    36

    Returns: "Possible"

  110. {72,24,472392,108,72,472392,648,72,108,54,52488,52488,108,27,27,108,72,72,5832,72,72,54,648,472392,8,8,72,5832,1944,472392,24,24,54,8,472392,5832,108,648,8,1944,5832,17496,17496,8,52488,24,27,27,1944,24}

    216

    Returns: "Possible"

  111. {864,13122,192,864,2187,864,512,864,864,864,1296,864,11664,118098,8748,11664,486,648,864,864,864,8748,5832,864,2187,768,4096,944784,157464,18432,864,2916,6144,864,864,384,1024,384,17496,19683,864,78732,2048,864,314928,864,512,864,2048,3888}

    864

    Returns: "Possible"

  112. {3,944784,256,162,32,20736,10368,15116544,162,177147,59049,20736,354294,729,1728,512,162,20736,15116544,18,9,81,2304,629856,118098,81,5184,4374,6,243,1458,41472,177147,162,5184,90699264,34992,2592,3456,648,81,81,256,3779136,81,41472,64,7558272,1728,2}

    324

    Returns: "Impossible"

  113. {15552,139968,46656,16,5832,243,1296,648,10368,3779136,11664,165888,11337408,54,139968,4,20736,104976,18,15552,1,314928,36,108,648,162,15552,10368,11337408,236196,9,4374,472392,419904,3888,1296,11337408,648,331776,34992,2,24,23328,11337408,1296,648,10368,11337408,5668704,54}

    5184

    Returns: "Possible"

  114. {864,16,13824,18,236196,1728,192,26244,6,3456,18,3456,16,324,6,3,2916,9,2916,48,3456,72,6,324,1,1728,6912,3456,26244,72,13824,256,1728,512,236196,324,864,3,13824,26244,13824,236196,9,1,432,432,96,864,972,384}

    108

    Returns: "Possible"

  115. {20736,354294,162,162,4608,1152,2592,8,576,162,19683,1296,354294,10368,81,81,41472,2187,81,162,10368,648,1296,162,81,216,192,162,2592,32,96,4374,3456,162,162,512,729,2592,486,5184,864,13824,2592,1296,162,81,13122,243,19683,648}

    324

    Returns: "Impossible"

  116. {5668704,5832,78732,13122,157464,236196,11664,11664,1458,69984,944784,5668704,354294,39366,177147,26244,6561,209952,2916,1417176,1458,944784,2187,6561,177147,729,69984,7776,13122,34992,1889568,52488,236196,209952,157464,6561,1944,972,2187,1458,944784,10368,419904,118098,1458,629856,157464,59049,6561,104976}

    10368

    Returns: "Impossible"

  117. {59049,17496,1296,52488,26244,157464,486,5832,13122,6561,1944,972,8748,972,13122,354294,472392,118098,472392,26244,236196,708588,157464,8748,26244,118098,972,39366,243,729,13122,118098,26244,13122,972,972,59049,2916,78732,708588,19683,236196,8748,6561,6561,5832,19683,1458,78732,1458}

    1296

    Returns: "Impossible"

  118. {8,4,4,32,16,256,32,8,4,8,64,162,256,128,16,64,4,16,64,128,32,4,64,128,32,32,8,4,4,16,128,128,256,32,8,8,16,4,64,8,32,16,32,32,16,256,32,32,4,16}

    162

    Returns: "Impossible"

  119. {48,384,768,32,48,16,1536,192,32,64,512,16,768,32,24,256,24,768,32,1536,1536,48,256,1536,128,64,192,384,64,96,256,256,8,384,192,768,96,384,1536,972,8,256,8,256,32,48,64,768,768,512}

    972

    Returns: "Impossible"

  120. {2,4,8,16,32,64}

    256

    Returns: "Impossible"

  121. {2, 12 }

    6

    Returns: "Impossible"

  122. {2 }

    2

    Returns: "Possible"

  123. {4, 9 }

    4

    Returns: "Impossible"

  124. {2, 3 }

    1

    Returns: "Possible"

  125. {24, 324, 3888, 486 }

    648

    Returns: "Possible"

  126. {2, 3 }

    3

    Returns: "Impossible"

  127. {2 }

    1

    Returns: "Impossible"

  128. {6, 9, 9 }

    6

    Returns: "Impossible"

  129. {1889568, 243, 1, 60466176 }

    7776

    Returns: "Impossible"

  130. {7776, 1728 }

    7776

    Returns: "Impossible"

  131. {1, 6 }

    2

    Returns: "Impossible"

  132. {1 }

    1

    Returns: "Possible"

  133. {2 }

    6

    Returns: "Impossible"

  134. {6, 27, 81, 729 }

    6

    Returns: "Impossible"

  135. {1, 6 }

    3

    Returns: "Impossible"

  136. {12, 2 }

    4

    Returns: "Impossible"

  137. {3, 18 }

    6

    Returns: "Impossible"

  138. {6, 6, 9 }

    6

    Returns: "Possible"

  139. {1, 6, 36, 216 }

    12

    Returns: "Impossible"

  140. {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 2, 6, 18, 54, 162, 486, 1458, 4374, 13122, 39366, 118098, 354294, 1062882, 3188646, 9565938, 28697814, 86093442, 258280326, 774840978, 4, 12, 36, 108, 324, 972, 2916, 8748, 26244, 78732, 236196, 708588 }

    3072

    Returns: "Impossible"

  141. {6, 36 }

    36

    Returns: "Possible"

  142. {1, 1, 1, 6, 6, 6 }

    2

    Returns: "Impossible"

  143. {6, 6, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9 }

    6

    Returns: "Possible"

  144. {6 }

    6

    Returns: "Possible"

  145. {1, 12 }

    12

    Returns: "Possible"

  146. {36, 36, 54 }

    36

    Returns: "Possible"

  147. {4, 9, 18 }

    4

    Returns: "Impossible"

  148. {36, 24 }

    36

    Returns: "Impossible"

  149. {4, 72, 27 }

    36

    Returns: "Possible"

  150. {3, 2, 3 }

    3

    Returns: "Possible"

  151. {4, 6, 6 }

    6

    Returns: "Possible"

  152. {1, 3, 9, 27, 81, 2, 6, 18, 54, 162, 4, 12, 36, 108, 324, 8, 24, 72, 216, 648, 16, 48, 144, 432, 1296, 32, 96, 288, 864, 2592, 64, 192, 576, 1728, 5184, 128, 384, 1152, 3456, 10368, 256, 768, 2304, 6912, 20736, 512, 1536, 4608, 13824, 41472 }

    1024

    Returns: "Impossible"

  153. {6, 1, 9 }

    9

    Returns: "Possible"

  154. {6, 36 }

    12

    Returns: "Impossible"

  155. {4, 4, 6 }

    4

    Returns: "Possible"

  156. {24, 36, 54 }

    216

    Returns: "Possible"

  157. {4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9 }

    6

    Returns: "Impossible"

  158. {36, 54, 216 }

    36

    Returns: "Possible"

  159. {3, 3, 2 }

    3

    Returns: "Possible"

  160. {2, 4, 8 }

    1

    Returns: "Impossible"

  161. {4, 6 }

    6

    Returns: "Impossible"

  162. {2, 2, 3 }

    2

    Returns: "Possible"

  163. {2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3 }

    4

    Returns: "Impossible"

  164. {60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 60466176, 1 }

    216

    Returns: "Impossible"

  165. {2916, 8, 13122, 139968 }

    5832

    Returns: "Possible"

  166. {1, 3, 18 }

    6

    Returns: "Impossible"

  167. {18, 12, 12 }

    12

    Returns: "Possible"

  168. {4, 6, 9 }

    6

    Returns: "Possible"

  169. {2, 12, 12 }

    6

    Returns: "Impossible"

  170. {16 }

    16

    Returns: "Possible"

  171. {2, 12 }

    4

    Returns: "Impossible"

  172. {3, 18, 4 }

    6

    Returns: "Possible"

  173. {15552, 864, 60466176 }

    7776

    Returns: "Impossible"

  174. {4, 48, 72 }

    36

    Returns: "Impossible"

  175. {2, 3 }

    6

    Returns: "Possible"

  176. {2, 6 }

    2

    Returns: "Possible"

  177. {3, 12, 18 }

    6

    Returns: "Possible"

  178. {4, 9, 4 }

    4

    Returns: "Possible"

  179. {967458816, 918330048, 859963392, 816293376, 764411904, 725594112, 644972544, 612220032, 573308928, 544195584, 483729408, 459165024, 429981696, 408146688, 382205952, 362797056, 322486272, 306110016, 286654464, 272097792, 254803968, 241864704, 214990848, 204073344, 191102976, 181398528, 161243136, 153055008, 143327232, 136048896, 127401984, 120932352, 107495424, 102036672, 95551488, 90699264, 80621568, 71663616, 68024448, 63700992, 60466176, 53747712, 51018336, 47775744, 45349632, 40310784, 35831808, 34012224, 31850496, 15116544 }

    30233088

    Returns: "Possible"

  180. {36 }

    36

    Returns: "Possible"

  181. {1, 6, 36, 216, 1296 }

    12

    Returns: "Impossible"

  182. {4, 3 }

    12

    Returns: "Possible"

  183. {4, 2, 6 }

    6

    Returns: "Possible"

  184. {6, 6, 9, 9 }

    6

    Returns: "Possible"

  185. {96 }

    96

    Returns: "Possible"

  186. {1990656, 216 }

    1990656

    Returns: "Possible"

  187. {486, 236196, 72, 48, 2592 }

    2592

    Returns: "Possible"

  188. {6, 1 }

    2

    Returns: "Impossible"

  189. {324, 18, 36 }

    36

    Returns: "Possible"

  190. {128, 23328, 972, 2187, 128 }

    128

    Returns: "Possible"

  191. {3, 9, 2 }

    6

    Returns: "Possible"

  192. {3, 18, 54, 4 }

    6

    Returns: "Possible"

  193. {36, 24, 36 }

    36

    Returns: "Possible"

  194. {2, 3, 2 }

    2

    Returns: "Possible"

  195. {18, 108 }

    36

    Returns: "Impossible"

  196. {6, 12 }

    6

    Returns: "Possible"

  197. {2, 3, 3 }

    3

    Returns: "Possible"

  198. {81, 243, 256, 324, 6912 }

    108

    Returns: "Possible"

  199. {1, 1, 1, 2, 1 }

    1

    Returns: "Possible"

  200. {3, 18, 6 }

    6

    Returns: "Possible"

  201. {2, 18, 108 }

    36

    Returns: "Impossible"

  202. {2, 9, 9, 12, 36 }

    2

    Returns: "Possible"

  203. {559872, 10077696, 96, 144 }

    2304

    Returns: "Impossible"

  204. {3 }

    3

    Returns: "Possible"

  205. {6, 36 }

    18

    Returns: "Impossible"

  206. {48, 1296, 2, 8, 4, 48 }

    324

    Returns: "Impossible"

  207. {2, 12, 9 }

    6

    Returns: "Possible"

  208. {36, 12, 2 }

    6

    Returns: "Impossible"

  209. {12, 18, 36 }

    18

    Returns: "Possible"

  210. {6, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9 }

    6

    Returns: "Impossible"

  211. {6, 4, 36 }

    6

    Returns: "Possible"

  212. {18, 2, 12 }

    6

    Returns: "Possible"

  213. {48 }

    48

    Returns: "Possible"

  214. {108, 18 }

    36

    Returns: "Impossible"

  215. {9, 6, 8 }

    6

    Returns: "Possible"

  216. {1, 3, 18, 36 }

    6

    Returns: "Impossible"

  217. {1, 6, 27 }

    6

    Returns: "Possible"

  218. {108, 18, 1024 }

    36

    Returns: "Possible"

  219. {6, 6, 36 }

    6

    Returns: "Possible"

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: