100x speed-up of prevailing "7ms" (fastest) solution
Intuition\n\nReuse the prime_factors_t c++ class which I attempted (and developed) in another problem\n\nGCD and LCM calculations are as simple as bitwise AND a
# Intuition\n\nReuse the `prime_factors_t` c++ class which I attempted (and developed) in another problem\n\nGCD and LCM calculations are as simple as bitwise AND and bitwise OR respectively in the `prime_factors_t` representation.\n\n# Approach\n\nUse the Excel file which I used in the development of `prime_factors_t` to initialize the `prime_factors_t::g_astCONST` variable and the `prime_factors_t::g_aauPRIME_NUMBER` variable, tailored for this problem.\n\nPossible values of `nums[i]` are finite (only 31). The `prime_factors_t` representations of numbers 1 to 30 are constructed at compile-time (use `constexpr`). Then using look-up table approach to convert `nums[i]` into `prime_factors_t` representation.\n\nUse the "traverse left-to-right" and "traverse right-to-left" pattern that draw my attention recently in another problem.\n\nCombine the results of "left-to-right" and "right-to-left" to obtain the `n + 1` candidates. The for-loop of this procedure is auto-vectorized.\n\nReturn the maximum score among the candidates.\n\n# Complexity\n- Time complexity:\n$$O(n)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    long long maxScore(vector<int>& nums);\n};\n\n\n\tstruct prime_factors_t : std::tuple<uint32_t>\n\t{\n\t\tusing tuple_t = std::tuple<uint32_t>;\n\n\t\tusing number_t = std::uint64_t;\n\t\tusing encode_t = std::uint32_t; // encoded form\n\n\t\tstruct const_t\n\t\t{\n\t\t\tencode_t uBit0;\n\t\t\tencode_t uMask;\n\t\t};\n\t\tconstexpr static const_t const g_astCONST[]\n\t\t{\n\t\t\t{(1u << 0),(15u << 0)},//2\n\t\t\t{(1u << 4),(7u << 4)},//3\n\t\t\t{(1u << 7),(3u << 7)},//5\n\t\t\t{(1u << 9),(1u << 9)},//7\n\t\t\t{(1u << 10),(1u << 10)},//11\n\t\t\t{(1u << 11),(1u << 11)},//13\n\t\t\t{(1u << 12),(1u << 12)},//17\n\t\t\t{(1u << 13),(1u << 13)},//19\n\t\t\t{(1u << 14),(1u << 14)},//23\n\t\t\t{(1u << 15),(1u << 15)},//29\n\t\t};\n\n\t\tconstexpr static number_t const g_aauPRIME_NUMBER[][4]\n\t\t{\n\t\t\t{2,4,8,16},\n\t\t\t{3,9,27,0},\n\t\t\t{5,25,0,0},\n\t\t\t{7,0,0,0},\n\t\t\t{11,0,0,0},\n\t\t\t{13,0,0,0},\n\t\t\t{17,0,0,0},\n\t\t\t{19,0,0,0},\n\t\t\t{23,0,0,0},\n\t\t\t{29,0,0,0},\n\t\t};\n\n\t\tconstexpr prime_factors_t() = default;\n\t\tconstexpr prime_factors_t(tuple_t&& that)\n\t\t\t: tuple_t(std::move(that))\n\t\t{\n\t\t}\n//\t\tusing tuple_t::tuple;\n\n\t\tconstexpr static std::tuple<encode_t, number_t> encode(number_t uNumber, size_t const zuStart, size_t const zuEnd, encode_t ulPrimeFactors)\n\t\t{\n\t\t\tfor (size_t i = zuStart; i < zuEnd && 1u < uNumber; ++i)\n\t\t\t{\n\t\t\t\tnumber_t const uPrimeNumber = g_aauPRIME_NUMBER[i][0];\n\n\t\t\t\tfor (encode_t uBit = g_astCONST[i].uBit0; uNumber % uPrimeNumber == 0; uNumber /= uPrimeNumber, uBit <<= 1)\n\t\t\t\t{\n\t\t\t\t\tulPrimeFactors |= uBit;\n\t\t\t\t}\n\t\t\t}\n\t\t\treturn{ ulPrimeFactors, uNumber };\n\t\t}\n\n\t\tconstexpr prime_factors_t(number_t uNumber)\n\t\t\t: tuple_t(std::get<0>(encode(uNumber >> std::countr_zero(uNumber), 1u, 10u, (1u << std::countr_zero(uNumber)) - 1u)))\n\t\t{\n\t\t}\n\n\t\tconstexpr static number_t decode(encode_t const ulPrimeFactors, size_t const zuStart, size_t const zuEnd, number_t uFactors)\n\t\t{\n\t\t\tfor (size_t i = zuStart; i < zuEnd && ulPrimeFactors >= g_astCONST[i].uBit0; ++i)\n\t\t\t{\n\t\t\t\tencode_t const uBits = ulPrimeFactors & g_astCONST[i].uMask;\n\n\t\t\t\tif (uBits)\n\t\t\t\t{\n\t\t\t\t\tuFactors *= g_aauPRIME_NUMBER[i][std::popcount(uBits) - 1u];\n\t\t\t\t}\n\t\t\t}\n\t\t\treturn uFactors;\n\t\t}\n\t\t//constexpr static number_t decode(encode_t ulPrimeFactors, size_t const zuStart, number_t uFactors)\n\t\t//{\n\t\t//\twhile (ulPrimeFactors)\n\t\t//\t{\n\t\t//\t\tsize_t const zuIndex0 = zuStart + std::countr_zero(ulPrimeFactors) / 2u;\n\n\t\t//\t\tunsigned const uIndex1 = std::popcount(encode_t(ulPrimeFactors & g_astCONST[zuIndex0].uMask)) - 1u;\n\n\t\t//\t\tulPrimeFactors &= ~g_astCONST[zuIndex0].uMask;\n\n\t\t//\t\tuFactors *= g_aauPRIME_NUMBER[zuIndex0][uIndex1];\n\t\t//\t}\n\t\t//\treturn uFactors;\n\t\t//}\n\n\t\tconstexpr operator number_t () const\n\t\t{\n\t\t\treturn decode(std::get<encode_t>(*this), 1u, 10u, 1u) << std::popcount(encode_t(std::get<encode_t>(*this) & g_astCONST[0].uMask));\n\t\t}\n\t};\n\tprime_factors_t gcd(prime_factors_t const& lhs, prime_factors_t const& rhs)\n\t{\n\t\treturn{ prime_factors_t::tuple_t(std::get<0>(lhs) & std::get<0>(rhs)) };\n\t}\n\tprime_factors_t lcm(prime_factors_t const& lhs, prime_factors_t const& rhs)\n\t{\n\t\treturn{ prime_factors_t::tuple_t(std::get<0>(lhs) | std::get<0>(rhs)) };\n\t}\n\n\n\nlong long Solution::maxScore(vector<int>& nums)\n{\n\tsize_t const n = nums.size();\n\tif (n == 0) return 0ll;\n\n\t// 1. prime factors representation of `nums`\n\tconstexpr static prime_factors_t aPrimeFactors[31]{ 1,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30 };\n\n\t// 2. left-to-right and right-to-left pattern\n\tstd::vector<prime_factors_t> vPrimeFactors_lcm_left;\n\tstd::vector<prime_factors_t> vPrimeFactors_gcd_left;\n\tstd::vector<prime_factors_t> vPrimeFactors_lcm_right;\n\tstd::vector<prime_factors_t> vPrimeFactors_gcd_right;\n\tvPrimeFactors_lcm_left.resize(n);\n\tvPrimeFactors_gcd_left.resize(n);\n\tvPrimeFactors_lcm_right.resize(n);\n\tvPrimeFactors_gcd_right.resize(n);\n\tvPrimeFactors_lcm_left.front() = aPrimeFactors[nums.front()];\n\tvPrimeFactors_gcd_left.front() = aPrimeFactors[nums.front()];\n\tvPrimeFactors_lcm_right.back() = aPrimeFactors[nums.back()];\n\tvPrimeFactors_gcd_right.back() = aPrimeFactors[nums.back()];\n\tfor (size_t i = 1, j = n - 2; i < n; ++i, --j)\n\t{\n\t\tvPrimeFactors_lcm_left[i] = lcm(vPrimeFactors_lcm_left[i - 1], aPrimeFactors[nums[i]]);\n\t\tvPrimeFactors_gcd_left[i] = gcd(vPrimeFactors_gcd_left[i - 1], aPrimeFactors[nums[i]]);\n\t\tvPrimeFactors_lcm_right[j] = lcm(vPrimeFactors_lcm_right[j + 1], aPrimeFactors[nums[j]]);\n\t\tvPrimeFactors_gcd_right[j] = gcd(vPrimeFactors_gcd_right[j + 1], aPrimeFactors[nums[j]]);\n\t}\n\n\t// 3. combine "left-to-right" and "right-to-left" results\n\tstd::vector<prime_factors_t> vCandidate_lcm;\n\tstd::vector<prime_factors_t> vCandidate_gcd;\n\tvCandidate_lcm.resize(1 + n);\n\tvCandidate_gcd.resize(1 + n);\n\tvCandidate_lcm[0] = vPrimeFactors_lcm_right.front();\n\tvCandidate_gcd[0] = vPrimeFactors_gcd_right.front();\n\tif (1 < n)\n\t{\n\t\tvCandidate_lcm[1] = *(vPrimeFactors_lcm_right.begin() + 1);\n\t\tvCandidate_gcd[1] = *(vPrimeFactors_gcd_right.begin() + 1);\n\n\t\tprime_factors_t const* __restrict pstPrimeFactors_lcm_left = vPrimeFactors_lcm_left.data();\n\t\tprime_factors_t const* __restrict pstPrimeFactors_gcd_left = vPrimeFactors_gcd_left.data();\n\t\tprime_factors_t const* __restrict pstPrimeFactors_lcm_right = vPrimeFactors_lcm_right.data() + 2;\n\t\tprime_factors_t const* __restrict pstPrimeFactors_gcd_right = vPrimeFactors_gcd_right.data() + 2;\n\t\tprime_factors_t* __restrict pstPrimeFactors_lcm = vCandidate_lcm.data() + 2;\n\t\tprime_factors_t* __restrict pstPrimeFactors_gcd = vCandidate_gcd.data() + 2;\n\n\t\tfor (size_t i = 0, i_end = n - 2; i < i_end; ++i) // info C5001: loop vectorized\n\t\t{\n\t\t\t//pstPrimeFactors_lcm[i] = lcm(pstPrimeFactors_lcm_left[i], pstPrimeFactors_lcm_right[i]);\n\t\t\t//pstPrimeFactors_gcd[i] = gcd(pstPrimeFactors_gcd_left[i], pstPrimeFactors_gcd_right[i]);\n\t\t\tstd::get<prime_factors_t::encode_t>(pstPrimeFactors_lcm[i]) = std::get<prime_factors_t::encode_t>(pstPrimeFactors_lcm_left[i]) | std::get<prime_factors_t::encode_t>(pstPrimeFactors_lcm_right[i]);\n\t\t\tstd::get<prime_factors_t::encode_t>(pstPrimeFactors_gcd[i]) = std::get<prime_factors_t::encode_t>(pstPrimeFactors_gcd_left[i]) & std::get<prime_factors_t::encode_t>(pstPrimeFactors_gcd_right[i]);\n\t\t}\n\t\tvCandidate_lcm.back() = *(vPrimeFactors_lcm_left.rbegin() + 1);\n\t\tvCandidate_gcd.back() = *(vPrimeFactors_gcd_left.rbegin() + 1);\n\t}\n\n\t// 4. calculate scores\n\tuint64_t uMaxScore = 0;\n\tfor (size_t i = 0, i_end = 1 + n; i < i_end; ++i)\n\t{\n\t\tuint64_t const uGCD = vCandidate_gcd[i];\n\t\tuint64_t const uLCM = vCandidate_lcm[i];\n\n\t\tuMaxScore = std::max(uMaxScore, (uGCD * uLCM));\n\t}\n\n\treturn (long long)(uMaxScore);\n}\n\n#include <iostream>\nstatic auto _______ = []() {\n    // turn off sync\n    std::ios::sync_with_stdio(false);\n    // untie in/out streams\n    std::cin.tie(nullptr);\n    return 0;\n}();\n\n```
['Bit Manipulation', 'Bitmask', 'C++']