Subtask 1

For the first subtask, we can iterate over each subset of arm lengths and count the number of unique prime factors for that subset. We can store the minimum number of primes factors for each size of the subset.

Time Complexity: ~\mathcal{O}(N \cdot 2^N)~

Subtask 2

For the second subtask, we can represent an arm as a bitmask of the prime factors it contains. Since there are only ~21~ primes less than or equal to ~75~, there are ~2^{21}~ possible bitmasks. We can keep track of how many arms have a bitmask that is a subset of the bits for each of the ~2^P~ bitmasks. Let ~m_i~ be the bitmask of arm ~i~. For each arm, we can go through each of the bitmasks and increment that bitmask's count if ~m_i~ is a submask of that bitmask.

To find the answer for each value of ~k~, we can iterate through each of the bitmasks that have a count of at least ~k~ and find the minimum number of bits in those bitmasks.

Let ~P~ be the number of primes less than ~75~.

Time Complexity: ~\mathcal{O}(N \cdot 2^P)~

Subtask 3

For the third subtask, we can use an idea similar to the second subtask. To speed up the solution, we will split the bitmask into two parts: the first ~A~ bits, and the last ~P-A~ bits. We will keep track of ~cnt[a][b]~, which stores the number of arms such that the last ~P-A~ bits evaluates to ~b~, and the first ~A~ bits is a submask of ~a~. For each value of ~N~, we will need to iterate through ~2^A~ bitmasks to update the ~cnt~ array.

Once this is done, we can go through each of the ~2^P~ bitmasks to find the number of arms that are a submask of that bitmask. This can be done by adding the values of ~cnt[a][b]~ such that ~a~ is the evaluation of the first ~A~ bits of that bitmask evaluates to ~a~, and ~B~ is a submask of the last ~P-A~ bits of that bitmask. The answer for this sum can be updated by checking if the number of bits in that bitmask is less than the current answer. With bitmask tricks, it is possible to iterate through all subsets for each of the ~2^P~ bitmasks in ~\mathcal{O}(2^A \cdot 3^{P-A})~.

Finally, remember to take the suffix minimum of the answer array, in case there are some values of ~k~ that do not have a bitmask that results in a sum equal to ~k~.

Here, it is optimal to choose ~A = 10~.

Some tricks for optimization include taking the transpose of ~cnt~ between the initial update, and the iteration over the bitmasks, as well as reversing the order of indices in the ~cnt~ array.

Time Complexity: ~\mathcal{O}(2^A \cdot (N + 3^{P-A}))~

Alternate Solution

wleung_bvg has no idea how to SOS DP, so please bear with him.

For those who do not like data structures, there is also a dynamic programming solution using a method known as Sum Over Subsets (SOS). SOS allows us to efficiently compute the sum of all ~arr[i]~ such that ~x \mathbin{\&} i = i~ for all values of ~x~, given an array ~arr~ of size ~2^N~ (~\&~ is the bitwise ~and~ operator).

Let ~S(x, i)~ be the set of all submasks that differ from ~x~ only in the first ~i~ bits. If the ~i^{th}~ bit of ~x~ is a ~0~, then it's clear that any masks with the ~i^{th}~ bit as ~1~ cannot be a submask of ~x~. Thus, all submasks that differ only in the first ~i~ bits must also only differ in the first ~i-1~ bits. It follows that ~S(x, i) = S(x, i-1)~.

If the ~i^{th}~ bit of ~x~ is a ~1~, then we can divide ~S(x, i)~ into two disjoint sets. The first set is all submasks that have the ~i^{th}~ bit as ~1~, and differ only in the first ~i-1~ bits. The second is the set of all submasks that have the ~i^{th}~ bit as ~0~ and differ only in the first ~i-1~ bits. Thus it follows that ~S(x, i) = S(x, i-1) \cup S(x \oplus 2^i, i-1)~ where ~\oplus~ is the bitwise ~xor~ operator).

It can be shown that these subset relations create overlapping subproblems, allowing for a dynamic programming solution by adding the values of the subsets. More information on SOS dynamic programming can be seen on a Codeforces article.

To set up the initial array, ~arr[x]~ contains the number of arms that have a mask equal to ~x~. Since all bitmasks are a subset of ~2^P~, we can solve the subset sum problem for that mask, and due to the nature of dynamic programming, ~dp[x][N-1]~ will contain the answer for each value mask ~x~. We can see that the subset relations form a directed acyclic graph, with ~S(x, -1)~ being nodes with an outdegree of ~0~ for all masks ~x~. This will be our base case for the dp. We will initialize ~dp[x][-1]~ to ~arr[x]~. From here, we can see that all ~S(x, i)~ will always depend on another set ~S(y, j)~ such that ~y < x~ or ~j < i~. Thus, we can compute ~dp[x][i]~ for all values of ~x~ and ~i~ by iterating over all masks in ascending order, and for each mask ~x~, compute ~dp[x][i]~ for all values of ~i~ in ascending order using the relation described above based on whether the ~i^{th}~ bit is set. Specifically, ~dp[x][i] = dp[x][i-1]~ if the ~i^{th}~ bit is ~0~, and ~dp[x][i] = dp[x][i-1] + dp[x \oplus 2^i][i-1]~ if the ~i^{th}~ bit is ~1~.

Once this is completed, the number of arms that have a mask that is a subset of ~x~ can be found at ~dp[x][N-1]~. The answer can then be recovered in a manner similar to the first solution for subtask 3.

Time Complexity: ~\mathcal{O}(N + P \cdot 2^P)~