一个长了一张数学脸的dp！！dp[ i ][ s ][ t ] 表示第 i 个数，sum为 s ，lcm下标为 t 时的个数。显然，一个数的因子的lcm还是这个数的因子，所以我们的第三维用因子下标代替lcm，可以有效的减少枚举量。
#include#include #include #include #include #include #include #define LL long long#define CLR(a, b) memset(a, b, sizeof(a))using namespace std;const int N = 1010;const int MOD = 1e9 + 7;int k, num, m;int dp[2][N][40];int ok[N], f[N][N];int gcd(int a, int b){ return b ? gcd(b, a % b) : a;}int lcm(int a, int b){ return a / gcd(a, b) * b;}int main(){ //freopen("input.txt", "r", stdin); int n, i, j, s, t, tmd = 0; while(scanf("%d%d%d", &n, &m, &k) != EOF) { CLR(dp, 0);num = 0; for(i = 1; i <= m; i ++) { if(m % i == 0) ok[num ++] = i; }//num不超过32 for(i = 0; i < num; i ++) { for(j = 0; j < num; j ++) { t = lcm(ok[i], ok[j]); for(s = 0; s < num; s ++) { if(ok[s] == t) { f[i][j] = s; break; } } } } for(j = 0; j < num; j ++) { dp[0][ok[j]][j] = 1; } for(i = 1; i < k; i ++) { for(s = 0; s <= n; s ++)//一定记得初始化 { for(t = 0; t < num; t ++) { dp[i & 1][s][t] = 0; } } for(j = 0; j < num; j ++) { for(s = i; s <= n - (k - i - 1) - ok[j]; s ++) { for(t = 0; t < num; t ++) { dp[i&1][s+ok[j]][f[t][j]]= (dp[i&1][s+ok[j]][f[t][j]]+dp[1-(i&1)][s][t]) % MOD; } } } } printf("%d\n", dp[(k - 1) & 1][n][num - 1]); } return 0;}