[Medium] EllysNumbers

일단 주어진 수열 S에 1이 포함되어있다면 빼고 문제를 푼 다음에 답에 *2 를 해주면 되므로 1을 빼놓고 생각하자. 수열 S에서 n을 만드는데 쓰일 가능성이 있는 것들과 없는 것들을 먼저 구분해보자. S[i] = p1^q1 * p2^q2 * ... * pm^qm 이라고 하자. (pk는 소수) 이 S[i]가 n을 만드는데 쓰일 가능성이 있으려면 모든 pk에 대해, n은 소인수 pk를 정확히 qk개 만큼 가져야 한다. S[i]를 n을 만드는데 사용한다면 나머지들은 S[i]와 서로소여야 하기 때문에 pk를 충당하는건 오로지 S[i]를 통해서만 가능하기 때문이다. 이를 통해 n을 만드는데 쓰일 가능성이 없는 것들을 우선 추려낼 수 있다. 그렇게 추려내고 남은 S[i]들의 소인수를 전부 모은 집합을 P라 하자. n의 소인수 중 P에 포함되지 않는 것이 존재할 수 있다. 이 경우엔 S[i]들을 갖고 절대 n을 만들지 못하므로 답은 0이다. 이제 남은 S[i] = p1^q1 * p2^q2 * ... * pm^qm 에 대해 n을 만들 때에 S[i]를 선택한다면 그 다음부터는 p1, p2, ..., pm 을 전혀 고려하지 않아도 된다. 따라서 S[i]를 선택하는 것이 아니라 집합 P에서 { p1, p2, ..., pm } 을 선택하는 것으로 볼 수 있다. 이제 문제를 해결하기 위해 이런 DP를 생각해볼 수 있다. D[i][s] = S[1]부터 S[i]까지 중에 적당히 골라서 소인수 집합 s를 완성시켰을 때 (s ⊂ P 여야 함) 이렇게 될 수 있는 경우의 수 = D[i-1][s] + D[i-1][s - set(S[i])] 답은 D[n][P] 일 것이다. P의 최대 크기는 어느정도 일까? n <= 10^18 이므로 최대한 작은 소인수들을 모아보면 2*3*5*7*11*13*17*19*23*29*31*37*41*43*47 이 10^18 이하면서 소인수를 가장 많이 넣을 수 있는 소인수열이다. 따라서 P의 최대 크기는 15 다. bitmask DP를 해도 충분한 정도의 제한이다. 시간복잡도는 O(n * 2^15) 500*2^15 크기의 배열을 선언하면 MLE가 날 수도 있으니 2*2^15 만큼만 선언하는 테크닉을 써야한다.