题目描述
猴猴最爱吃香蕉了。每天猴猴出门都会摘很多很多的香蕉，每个香蕉都有一个甜度，猴猴不一定要把所有的香蕉都吃掉，猴猴每天都有一个心情值K，猴猴希望当天吃的香蕉满足这么一个条件，这些香蕉的甜度乘积恰好等于K，但是猴猴并不知道有多少种方法，于是猴猴把这个问题交给你。
题目解析
背包，依题目可得：只有
K
K
K的约数才能作为转移，所以我们可以筛出来
K
K
K的约数
枚举香蕉的甜度
a
a
a和心情值
b
b
b（都是
K
K
K的约数），则有转移方程
f
[
b
]
+
=
f
[
b
/
a
]
f[b]+=f[b/a]
f[b]+=f[b/a]
若当前香蕉的甜度和心情值相等，
f
[
a
]
+
+
f[a]++
f[a]++即可
防止浪费空间，用了
m
a
p
map
map。
代码
#include<bits/stdc++.h>
#define M 1000000007
using namespace std
;
map
<int,int> f
;
int T
,n
,k
,cnt
;
int a
[1000005],b
[1005];
int main()
{
scanf("%d",&T
);
while(T
--)
{
f
.clear();cnt
=0;
scanf("%d%d",&n
,&k
);
for(int i
=1;i
<=sqrt(k
);i
++)
if(k
%i
==0)
{
a
[++cnt
]=i
;
if(i
*i
!=k
) a
[++cnt
]=k
/i
;
}
sort(a
+1,a
+1+cnt
);
for(int i
=1;i
<=n
;i
++) scanf("%d",&b
[i
]);
for(int i
=1;i
<=n
;i
++)
{
for(int j
=cnt
;j
>=1;j
--)
if(a
[j
]%b
[i
]==0)
{
(f
[a
[j
]]+=f
[a
[j
]/b
[i
]])%=M
;
if(a
[j
]==b
[i
]) (f
[a
[j
]]+=1)%=M
;
}
}
cout
<<f
[a
[cnt
]]<<endl
;
}
}
