51nod 1354：选数字

题目链接：

题目大意：有$T(T \leqslant 20)$组数据，每组给出$n(n \leqslant 1000)$个数和$K(K \leqslant 100,000,000)$，问在这$n$个数中选取若干个，积为$K$的方案数有多少.

DP+离散化

与01背包类似，定义状态$dp[i][j]$为前$i$个数中选取若干个数，积为$j$的方案数.

但积过大（$K \leqslant 100,000,000$），考虑到实际有用状态并不多，有用状态为$dp[i][d]$，其中$d$为$K$的因数.

故可以预处理出$K$的因数，将其离散化，从而把第二维降到$D(K)$，$D(K)$表示$K$的因子数.

算法时间复杂度为$O(n \times D(K) \times lg(D(K)))$，$lg$为离散化所带来的时间.

代码如下：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #define N 1005 6 using namespace std; 7 typedef long long ll; 8 const ll M=1000000007; 9 int T,n,K,a[N],k,fact[N],dp[N][N],t,ans;10 int main(void){11     scanf("%d",&T);12     while(T--){13         memset(dp,0,sizeof(dp));14         scanf("%d%d",&n,&K);15         for(t=1,k=0;t*t