POJ3421 X-factor Chains

思路

• 先求出x的质因子个数，包含重复的，这就是题目所求的最大长度
  • 使用质因子分解，然后将幂次累加即可
• 这些质因子组成的包含重复元素的序列的全排列个数，就是题目所求的最长序列个数
  • 法一：使用公式：
    
  • 法二：使用dfs
    参考leetcode 47. 全排列 II

代码1(使用公式)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long LL;

const int N = 2010;
int factor[N], degree[N], cnt; // factor是质因子, degree是质因子阶数
LL fac[30];

void divide(int x)
{
    for (int i = 2; i <= x / i; i++)
    {
        int s = 0;
        if (x % i == 0)
        {
            while (x % i == 0)
            {
                s++;
                x /= i;
            }
        }
        if (s > 0)
        {
            factor[cnt] = i;
            degree[cnt] = s;
            cnt++;
        }
    }
    if (x > 1)
    {
        factor[cnt] = x;
        degree[cnt] = 1;
        cnt++;
    }
}

// 预处理阶乘
void init()
{
    fac[0] = 1;
    for (int i = 1; i <= 20; i++)
    {
        fac[i] = i * fac[i - 1];
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int x;
    init();
    while (scanf("%d", &x) != EOF)
    {
        cnt = 0;
        divide(x);
        int max_len = 0;
        for (int i = 0; i < cnt; i++)
        {
            max_len += degree[i];
        }
        LL max_num = fac[max_len];
        for (int i = 0; i < cnt; i++)
        {
            max_num /= fac[degree[i]];
        }
        cout << max_len << ' ' << max_num << endl;
    }
    return 0;
}

代码2(使用dfs)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long LL;

const int N = 2010;
int factor[N], cnt; // factor是所有质因子，包含重复
bool vis[N];

void divide(int x)
{
    for (int i = 2; i <= x / i; i++)
    {
        while (x % i == 0)
        {
            factor[cnt++] = i;
            x /= i;
        }
    }
    if (x > 1)
    {
        factor[cnt++] = x;
    }
}

void dfs(int idx, int &ans)
{
    if (idx == cnt)
    {
        ans++;
        return;
    }
    for (int i = 0; i < cnt; i++)
    {
        if (vis[i] || (i && factor[i - 1] == factor[i] && !vis[i - 1]))
        {
            continue;
        }
        vis[i] = true;
        dfs(idx + 1, ans);
        vis[i] = false;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int x;
    while (scanf("%d", &x) != EOF)
    {
        cnt = 0;
        memset(vis, 0, sizeof vis);
        divide(x);
        int max_num = 0;
        dfs(0, max_num);
        cout << cnt << ' ' << max_num << endl;
    }
    return 0;
}