X-factor Chain（信息学奥赛一本通 1628）

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const ll N=1100000;
 5 int c[21];
 6 ll f[N];
 7 ll fac(ll x)
 8 {
 9     if(f[x])return f[x];//记忆化搜索 
10     f[x]=x*fac(x-1);
11     return f[x];
12 }
13 int main()
14 {
15     ll x;f[1]=1;
16     while(~scanf("%lld",&x))
17     {
18         ll cnt=0,ans=0;//每次都要更新 
19         memset(c,0,sizeof(c));
20         ll n=x;
21         for(ll i=2;i*i<=x;i++)
22         {
23             if(n%i==0)
24             {
25                 cnt++;//cnt存x可分解出的质因子的种数 
26                 while(n%i==0)
27                 {
28                     n/=i;
29                     c[cnt]++;//第几种质因子在x里出现的个数 
30                     ans++;//ans指x里一共有多少个质因子 
31                 }
32             }
33         }
34         if(n>1)//如果还有一个大于sqrt(n)的质数 
35         {
36             c[++cnt]++;
37             ans++;
38         }
39         printf("%lld ",ans);
40         ll nn=fac(ans);//nn=ans!
41         for(int i=1;i<=cnt;i++)
42             nn/=fac(c[i]);
43         printf("%lld\n",nn);
44     }
45     return 0;
46 }