思路：
dp[i][j][k]表示满足前i个数，和为j，lcm为k的数目。
设a为解的第i+1个数。
那么状态转移就为
dp[i+1][j+a][lcm(a,k)]+=dp[i][j][k]。
但是由于三维开不了，所以用滚动数组。
代码如下：
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#define ll __int64
#define pi acos(-1.0)
#define MAX 1001
#define M 1000000007
using namespace std;
int num[MAX],LCM[MAX][MAX],dp[][MAX][MAX],cnt;
int gcd(int a,int b)
{
while(b){
int t=a;
a=b;
b=t%b;
}
return a;
}
int lcm(int a,int b)
{
return a/gcd(a,b)*b;
}
void init()//预处理出lcm
{
int i,j;
for(i=;i<MAX;i++){
LCM[i][i]=i;
for(j=;j<i;j++)
LCM[j][i]=LCM[i][j]=lcm(i,j);
}
}
int main(){
int t,n,m,k,i,j,now,v;
init();
while(scanf("%d%d%d",&n,&m,&k)!=EOF){
cnt=;
for(i=;i<=m;i++)
if(m%i==)
num[cnt++]=i;
now=;
for(i=;i<=n;i++)//不要用memset
for(j=;j<cnt;j++)
dp[now][i][num[j]]=;
dp[now][][]=;
for(t=;t<=k;t++){
now^=;
for(i=;i<=n;i++)//不要用memset
for(j=;j<cnt;j++)
dp[now][i][num[j]]=;
for(i=t-;i<=n;i++){
for(j=;j<cnt;j++){
if(dp[now^][i][num[j]]==) continue;
for(v=;v<cnt;v++){
int s=i+num[v];
int l=LCM[num[j]][num[v]];
if(s>n||m%l!=) continue;
dp[now][s][l]+=dp[now^][i][num[j]];
dp[now][s][l]%=M;
}
}
}
}
printf("%d\n",dp[now][n][m]);
}
return ;
}