poj3421(X-factor Chains)质因数分解

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

Sample Output

题意：给定一个正整数 X，求满足1 < X1 < X2 < ... < Xm-1 < X且前一个数可以整除相邻的后一个数的最大m和这种情况下方法数。

题解：第一个想到的是深搜，枚举X因子，然后对除以因子后的数DFS，想想也会超时。。。然后往数学方面想，参考了大牛的博客后才恍然大悟。首先对X分解质因数，设X = a1^q1 * a2^q2 * ... * an^qn，那么最长的数链肯定是每次从n个质因子中取一个数，然后累乘到前一个数上面，所以最大的m就是q1+q2+...+qn。方法数就是每次取的不同取法数，因为每个质因子都有重复，所以答案为质因子个数之和的全排列，再除以每个质因子个数的全排列。

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <map>
#include <vector>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <numeric>
#include <iomanip>
#include <limits>
#include <new>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <ctime>
using namespace std;

typedef long long ll;

ll fact[18] = {1};

vector<int> div(int x)
{
    vector<int> pow;
    for (int i = 2; i * i <= x; ++i)
    {
        int cnt = 0;
        while (x % i == 0)
        {
            x /= i;
            cnt++;
        }
        pow.push_back(cnt);
    }
    if (x != 1)
        pow.push_back(1);
    return pow;
}

int main()
{
    for (int i = 1; i < 18; ++i)
        fact[i] = i * fact[i-1];
    int x;
    while (~scanf("%d", &x))
    {
        vector<int> pow = div(x);
        ll sump = accumulate(pow.begin(), pow.end(), 0);
        ll mulp = 1;
        for (vector<int>::iterator it = pow.begin(); it != pow.end(); ++it)
            mulp *= fact[*it];
        printf("%lld %lld\n", sump, fact[sump]/mulp);
    }
    return 0;
}

算法码上来文章被收录于专栏

公众号「算法码上来」。godweiyang带你学习算法，不管是编程算法，还是深度学习、自然语言处理算法都一网打尽，更有各种计算机新鲜知识和你分享。别急，算法码上来。