题目描述

输入正整数 $X$，求 $X$的大于1的因子组成的满足任意前一项都能整除后一项的严格递增序列的最大长度，以及满足最大长度的序列的个数。

样例

2
3
4
10
100

1 1
1 1
2 1
2 2
4 6

算法

不知道叫啥算法,感觉和线性筛有不同,有相同的地方,是在<<挑战程序设计竞赛>>上看到的

这里用map[HTML_REMOVED] 来存n的质因子及其个数,map[i] = cnt: 表示i这个质因子可以被n整除cnt次.

接下来就好算了,长度是质因子次数相加,个数是一个简单的排列组合,细节其他题解都讲了,我就不在说一遍了.

y总的代码只求了一遍小于N的每个数的最小质因子,以后就不用求了,但是我的代码每组数据都会求一次感觉效率相比低一点

代码

#include <iostream>
#include <cstdio>
#include <map>

using namespace std;

typedef long long ll;

map<int, int> fenjie(int n)
{
    map<int, int> res;
    for(int i = 2; i <= n; ++i)
    {
        while(n % i == 0)
        {
            res[i]++;
            n /= i;
        }
    }
    return res;
}

int main()
{
    int n;
    while(cin >> n)
    { 
        map<int,int> ans = fenjie(n);
        int len = 0;
        ll cnt = 1;
        for(auto i: ans) len += i.second;
        for(int i = 1; i <= len ; i ++) cnt *= (ll)i;

        for(auto i : ans)
            for(int j = 1; j <= i.second; j ++)
                cnt /= (ll)j;

        printf("%d %lld\n", len, cnt);
    }
    return 0;
}