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;
}