「Test」猴猴吃香蕉

题意：猴猴每天会摘很多香蕉，每个香蕉有一个甜度。猴猴每天有一个心情值 $K(K\le 100000000)$，猴猴希望每天吃的香蕉的甜度乘积恰好等于 $K$，求每天的方法数(对 $10 ^9 +7$ 取模)。

解析：这题一看就是个很明显的背包。

但是由于 $K$ 过大，所以一个一个转移是不行的。由于要求乘积等于 $K$，所以只用转移 $K$ 的约数即可。所以先求出 $K$ 的约数，排序(很重要！！！)，然后依次转移即可，状态转移方程如下：

$$dp[p]=dp[p]+dp[\frac{p}{a[i]}]\ \ (a[i]|p)\\ dp[p]=dp[p]+1\ \ (p=a[i])$$

其中 $p$ 为 $K$ 的约数。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<map>
#define INF 1e9
using namespace std;
const int maxn=1010;
const int mod=1e9+7;
int d,n,a[maxn],cnt;
long long p[maxn*100],k;
map<long long,long long> dp;
int main()
{
	freopen("banana.in","r",stdin);
	freopen("banana.out","w",stdout);
	scanf("%d",&d);
	while(d--)
	{
		cnt=0;
		dp.clear();
		scanf("%d%lld",&n,&k);
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i]);
		int q=sqrt(k);
		for(int i=1;i<=q;i++)
			if(k%i==0)
			{
				p[++cnt]=i;
				if(i*i!=k)
					p[++cnt]=k/i;
			}
		sort(p+1,p+cnt+1);
		for(int i=1;i<=n;i++)
		{
			if(!a[i])
				continue;
			for(int j=cnt;j>=1;j--)
				if(p[j]%a[i]==0)
				{
					dp[p[j]]=(dp[p[j]]%mod+dp[p[j]/a[i]]%mod)%mod;
					if(p[j]==a[i])
						dp[p[j]]=(dp[p[j]]%mod+1)%mod;
				}
		}
		printf("%lld\n",dp[k]%mod);
	}
	return 0;
}