dp还是比较好想的，但是时间还是比较坑的。
要预处理还加些优化才行 。
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <algorithm> #include <math.h> #include <map> #include <queue> #include <sstream> #include <iostream> using namespace std; #define INF 0x3fffffff #define MOD 1000000007 int n,m,k; int dp[101][1010][35]; int save[1010][1010]; int g[35]; int cnt=0; int mark[1100]; //bool mark1[1100][1100]; int gcd(int x,int y) { int tmp; while(x) { tmp=x; x=y%x; y=tmp; } return y; } int lcm(int x,int y) { return x*y/gcd(x,y); } int main() { //freopen("C:\Users\Administrator\Desktop\in.txt","r",stdin); //freopen("C:\Users\Administrator\Desktop\in.txt","w",stdout); for(int i=1;i<=1000;i++) for(int j=1;j<=1000;j++) { save[i][j]=lcm(i,j); } //提前预处理 while(scanf("%d%d%d",&n,&m,&k)!=EOF) { //memset(mark1,0,sizeof(mark1)); //memset(mark,0,sizeof(mark)); memset(dp,0,sizeof(dp)); cnt=0; for(int i=1;i<=m;i++) if(m%i==0) { mark[i]=cnt; g[cnt++]=i; } dp[0][0][0]=1; //mark1[0][0]=1; int tmp,tmp1,tmp2; for(int i=0;i<k;i++) //对于k个数 { for(int j=i;j<=n;j++) { //if(mark1[i][j]==0) continue; for(int p=0;p<cnt;p++) { tmp2=dp[i][j][p]; if(tmp2==0) continue; for(int s=0;s<cnt;s++) //选择g[s] { if(g[s]+j > n-(k-i)+1) break; tmp1=g[s]; tmp=mark[ save[ g[p] ][ tmp1 ] ]; dp[i+1][ j+tmp1 ][ tmp ]=(dp[i+1][ j+tmp1 ][ tmp ]+tmp2)%MOD; //if(dp[i+1][ j+tmp1 ][tmp]>MOD) dp[i+1][ j+tmp1 ][tmp]-=MOD; } } } } printf("%d ",dp[k][n][cnt-1]); } return 0; }