X-因子链(factor)【DP】【数论】

>Description
给一个正整数X，一个长度为m的X-因子链是指这样一个序列：X0=1，X1，X2，。。。，Xm=X知足：Xi<Xi+1同时Xi|Xi+1(Xi+1能被Xi整除)
要求X-因子链的最大长度Len和长度为Len的X-因子链的数量。javascript

>Input
一个正整数Xhtml

>Output
一行，两个整数，分别表示最大长度和该长度链的种数。java

对于20%的数据：X<=20,000;
对于100%的数据：X<=2^31;且保证因子链最大长度小于等于20;ios

>解题思路
我用的dp就能够过了，不过跟题解的好像不太同样web

题目大意：
输入X，找到符合下列要求的序列最长长度len及长度为len的序列种数app

1. 上升序列
2. 最后一个数为X
3. 后一位数能被前一位数整除

一开始我看到这道题并无什么思路，因而我就开始打dp
设 $f[i][j]$为长度为i，且第i个数为j的方案数
对于第 $i$个数 $j$，第 $i-1$个数显然只能填 $j$的因数，设 $t$为 $j$的因数，得出状态转移方程： $f[i][j]=Σf[i-1][t]$
可是这样20 * X * X确定不行可能20分都没有，因此咱们再优化一下svg

样例给的X是100，100的因数有：1(1不能填因此无论它)、二、四、五、十、20、2五、50、100
对于最后一个数X，前一个数咱们只能填100前面这7个因数中的一个，因此咱们能够预处理100的因数，只在因数中进行转移。咱们又能够发现对于100的因数的因数，也同是100的因数，如50的因数：二、五、十、2五、50，也同是100的因数优化

因此得出结论：只有X的因数才会贡献答案，因此咱们预处理X的因数而后进行转移就好了spa

>代码code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define int long long
#define N 1000005
using namespace std;

int X, f[25][N], s[N];

signed main()
{
	scanf ("%lld", &X);
	for (int i = 2; i < sqrt (X); i++)
	  if (X % i == 0) s[++s[0]] = i, s[++s[0]] = X / i;
	if (sqrt (X) * sqrt (X) == X) s[++s[0]] = sqrt (X);
	s[++s[0]] = X; //答案求的是最后一个数为X，因此贡献答案的序列也要加上X
	sort (s + 1, s + 1 + s[0]); //从小到大排序使得单调上升
	for (int i = 1; i <= s[0]; i++) f[1][i] = 1; //预处理
	
	for (int i = 2; i <= 20; i++)
	  for (int j = 1; j <= s[0]; j++)
	    for (int t = 1; t < j; t++) //保持上升序列
	      if (s[j] % s[t] == 0) f[i][j] += f[i - 1][t];
	      
	for (int i = 20; i >= 1; i--) //题目给出的序列最长为20，因此从二十开始枚举看看有没有答案
	  if (f[i][s[0]])
	  {
	  	printf ("%lld %lld", i, f[i][s[0]]);
	  	break;
	  }
	return 0;
}