poj3421 X-factor Chains-白红宇

poj3421 X-factor Chains

阅读量：5066 次

发布时间：2019-06-12

本文共 1601 字，大约阅读时间需要 5 分钟。

题意：

Description

Given a positive integer X, an X-factor chain of length m is a sequence of integers,

1 = X₀, X₁, X₂, …, X_m = X

satisfying

X_i < X_i₊₁ and X_i | X_i₊₁ where a | b means a perfectly divides into b.

Now we are interested in the maximum length of X-factor chains and the number of chains of such length.

Input

The input consists of several test cases. Each contains a positive integer X (X ≤ 2²⁰).

Output

For each test case, output the maximum length and the number of such X-factors chains.

Sample Input

23410100

Sample Output

1 11 12 12 24 6

思路：

一开始想到dp。令dp[i][j]表示长度为i，以j结尾的链的个数，于是dp[i+1][k] += dp[i][j] (j为k的因子)，然而复杂度高，并不会优化。

后来发现要想链最长，只能从1开始，每次乘上这个数的某个质因子才行。于是就变成了分解质因子+排列组合的问题。

实现：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
           7 using namespace std; 8 typedef long long ll; 9 10 ll fac[21];11 int x;12 13 void init()14 {15 fac[0] = 1;16 for (ll i = 1; i <= 20; i++)17 fac[i] = fac[i - 1] * i;18 }19 20 map
           
             prime_factor(int n)21 {22 map
            
              res;23 for (int i = 2; i * i <= n; i++)24 {25 while (n % i == 0)26 {27 res[i]++;28 n /= i;29 }30 }31 if (n != 1)32 res[n] = 1;33 return res;34 }35 36 int main()37 {38 init();39 while (scanf("%d", &x) != EOF)40 {41 map
             
               f = prime_factor(x);42 map
              
               ::iterator it;43 ll res = 1;44 int cnt = 0;45 for (it = f.begin(); it != f.end(); it++)46 {47 res *= fac[it->second];48 cnt += it->second;49 }50 printf("%d %lld\n", cnt, fac[cnt] / res);51 }52 return 0;53 }

转载于:https://www.cnblogs.com/wangyiming/p/6443982.html

你可能感兴趣的文章