对于一个数来说，它的除数是确定的，那么它的前驱也是确定的，而起点只能是1或2，所以只要类似筛法先预处理出每个数的除数个数
，然后递推出每个数往前的延伸的链长，更新最大长度，记录对应数字。找到maxn以后，根据最后一个数找到前驱，并记录到ans数组中。
代码来自队友
#include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> #include<vector> #include<queue> #include<string> #include<iostream> #include<set> #include<map> #define mod 1000000007 #define inf 1000000001 #define big 1570000 using namespace std; int d[big+1]; int dp[big+1]; int ans[big+1]; void find() { for (int i = 1; i <big; i++) { for (int j = i; j <= big; j += i) d[j]++; } } int main() { find(); dp[1] = 1; dp[2] = 1; int maxn = 0; int re; for (int i = 3; i <=big; i++) { dp[i] = dp[i - d[i]] + 1; if (dp[i] > maxn) { maxn = dp[i]; re = i; } } for (int i = maxn; i >= 0; i--) { ans[i] = d[re]; re -= d[re]; } int n; scanf("%d", &n); if (n > maxn) printf("Impossible\n"); else { for (int i = 1; i < n; i++) { printf("%d ", ans[i]); } printf("%d\n", ans[n]); } return 0; }
原文：http://www.cnblogs.com/jerryRey/p/4719737.html