题目描述

给定正整数X，长度为m的X因子链(不包括X0)为，

1 = X0，X1，X2，…，Xm = X

满足:

Xi <Xi + 1和Xi | Xi + 1其中| 表示整除

求X因子链的最大长度以及该长度的方案数。$(X ≤ 2^{20})$

Input

2
3
4
10
100

Output

1 1
1 1
2 1
2 2
4 6

题解

由x数链的性质可以发现，将n分解为其质因数相乘的形式后，数链中任何一个数必定是这些质因数的某个组合，且任意相邻的2个质因数中后面的数必定是在前面的数的质因数的组合的基础上再乘上另外的一个质因数。(例如10=2 * 5 ，对应的两种方案为1,2,10和1,5,10)，所以很容易发现，数链的长度就是其质因数的次数的总和，然后将质因数泛化成物品，质因数的次数为每类物品的数量，则最后的方案就是求这些物品的多重集总排列。套用公式即可。

• 多重集合总排列公式：
  设第i类物品数量为ni。另n=n1+n2+n3+…+ni
  则总排列数量：n! / (n1!n2!n3!…ni!)

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<cmath>
using namespace std;
int dx[]={-1,0,1,0,0},dy[]={0,1,0,-1,0};
typedef pair<int,int> PII;
typedef long long LL;
const int INF=0x3f3f3f3f;

const int N=21;
LL fac[N];
int n;

void init(int n)
{
    fac[0]=1;
    for(int i=1;i<=n;i++)
        fac[i]=fac[i-1]*i;
}

int main()
{
    init(N-1);

    while(~scanf("%d",&n))
    {
        LL fm=1;
        int sum=0;
        for(int i=2;i*i<=n;i++)
            if(n % i == 0)
            {
                int s=0;
                while(n % i == 0) s++,n/=i;
                fm*=fac[s];
                sum+=s;
            }
        if(n > 1) sum++;

        LL fz=fac[sum];
        cout<<sum<<' '<<fz/fm<<endl;
    }

    //system("pause");
}