题目描述

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

输入格式

输入包含多组数据，每组数据占一行，包含一个正整数表示 X。

输出格式

对于每组数据，输出序列的最大长度以及满足最大长度的序列的个数。

每个结果占一行。

数据范围

1≤X≤220

输入样例：

2
3
4
10
100

输出样例：

1 1
1 1
2 1
2 2
4 6

解题思路

算术基本定理：任何大于1的正整数都可以唯一地分解为若干质因子乘积的形式.
根据题意不难发现： 
求最大长度即求：各个质因子出现的次数之和.
求满足最大长度的序列个数即求：所有质因子出现的次数的总和的阶乘 / 各个质因子出现次数的阶乘的积

C ++代码

#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = (1 << 20) + 10;

int primes[N];//存质数
int minp[N];//存最小质因子
int cnt;
bool st[N];//用于表示对应元素是否被筛过

//线性筛法    ---- 用于求1 ~ n之间的所有质数以及对应的最小质因子
void get_primes(int n){
    for(int i = 2; i <= n; i ++){
        if(!st[i]) minp[i] = i, primes[cnt ++] = i;
        for(int j = 0; primes[j] * i <= n; j ++){
            st[primes[j] * i] = true;
            minp[primes[j] * i] = primes[j];
            if(i % primes[j] == 0) break;
        }
    }
}

int main(){
    get_primes(N);

    int x;
    while(scanf("%d", &x) != -1){
        //tol用于记录最大长度,k表示第i个质因子的下标,k = 0对应第一个质因子下标
        int tol = 0, k = 0;
        int sum[N];//用于记录每个质因子出现的次数

        //依次处理各个质因子, 求出对应质因子出现的次数
        while(x > 1){
            int p = minp[x];//取出最小质因子
            sum[k] = 0;

            //处理当前质因子,求其出现的次数
            while(x % p == 0){
                sum[k] ++;
                tol ++;
                x /= p;
            }
            k ++;//准备处理下一个质因子
        }

        //求所有质因子出现总次数的全排列
        LL res = 1;
        for(int i = 1; i <= tol; i ++) res *= i;

        //去除各个质因子重复出现的次数
        for(int i = 0; i < k; i ++){
            for(int j = 1; j <= sum[i]; j ++){
                res /= j;
            }
        }

        printf("%d %lld\n", tol, res);
    }
}