明显是一道水题，但确不会做
如果把数给分解了之后有n个质因子。那么就是求n个点可以有多少种二叉树，然后把这n个质因子放进去就行了
求多少种二叉树就是dp，放质因子就是一个可重排列数
1 #include<stdio.h>
2 #include<iostream>
3 #include<string>
4 #include<vector>
5 #include<map>
6 #include<queue>
7 #include<algorithm>
8 #define M 1000
9 #define clr(x) memset(x,0,sizeof(x))
10 #define _clr(x) memset(x,-1,sizeof(x))
11 #define fr(i,a,b) for(int i=a;i<b;++i)
12 #define pf printf
13 #define sf scanf
14 #define pb push_back
15 #define mp make_pair
16 #define ll long long
17 #define debug 1
18 using namespace std;
19 const int maxs=1000000;
20 int pr[1000000],is[maxs+10],len;
21 int e[1000000],cnt;
22 void Frac(ll n)
23 {
24 cnt=0;
25 fr(i,0,len)
26 {
27 if((ll)pr[i]*pr[i]>n)break;
28 //pf("pr=%d\n",pr[i]);
29 if(n%pr[i]==0)
30 {
31 e[cnt]=0;
32 while(n%pr[i]==0)
33 {
34 n/=pr[i];
35 ++e[cnt];
36 }
37 ++cnt;
38 }
39 }
40 if(n>1)
41 {
42 e[cnt++]=1;
43 }
44 }
45 void getPrime()
46 {
47 len=0;
48 clr(is);
49 for(int i=2;i<maxs;++i)
50 {
51 if(!is[i])
52 {
53 pr[len++]=i;
54 }
55 for(int j=0;j<len&&(ll)pr[j]*i<maxs;++j)
56 {
57 is[pr[j]*i]=1;
58 if(i%pr[j]==0)break;
59 }
60 }
61 }
62 int p[1000000],exp[1000000],c;
63 ll pow(int a,int b)
64 {
65 ll ret=1;
66 while(b>0)
67 {
68 if(b&1){ret*=a;}
69 a*=(ll)a;
70 b>>=1;
71 }
72 return ret;
73 }
74 ll cal()
75 {
76 int tot=0;
77 for(int i=0;i<cnt;++i)
78 {
79 tot+=e[i];
80 }
81 //pf("c:\n");
82 //pf("tot=%d\n",tot);
83 c=0;
84 for(int i=0;i<len;++i)
85 {
86 if(pr[i]>tot)break;
87 p[c]=pr[i];
88 exp[c]=0;
89 int tem=tot;
90 while(tem>0)
91 {
92 exp[c]+=tem/p[c];
93 tem/=p[c];
94 }
95 // pf("pc=%d expc=%d\n",p[c],exp[c]);
96 ++c;
97 }
98 for(int i=0;i<cnt;++i)
99 {
100 int ret=e[i];
101 for(int j=0;j<len;++j)
102 {
103 if(pr[j]>ret)break;
104 int pos=lower_bound(p,p+c,pr[j])-p;
105 int tem=ret;
106 while(tem>0)
107 {
108 exp[pos]-=tem/pr[j];
109 tem/=pr[j];
110 }
111 }
112 }
113 ll res=1;
114 for(int i=0;i<c;++i)
115 {
116 res*=pow(p[i],exp[i]);
117 }
118 return res;
119 }
120 ll dp[1000000];
121 ll dfs(int n)
122 {
123 // if(n>1000000)return 1;
124 if(dp[n])return dp[n];
125 ll ret=0;
126 for(int i=1;i<=n/2;++i)
127 {
128 ll tem=dfs(i)*dfs(n-i);
129 if(i!=n-i)tem*=2;
130 ret+=tem;
131 }
132 return dp[n]=max(ret,(ll)1);
133 }
134
135 int main()
136 {
137
138 int n;
139 getPrime();
140 clr(dp);
141 freopen("in.txt","r",stdin);
142 //freopen("out1.txt","w",stdout);
143 while(sf("%d",&n)>0)
144 {
145 //ft.clear();
146 Frac(n);
147 int tot=0;
148 fr(i,0,cnt)
149 tot+=e[i];
150 //pf("tot=%d\n",tot);
151 ll ans=dfs(tot);
152 ans*=cal();
153 pf("%lld\n",ans);
154 }
155
156 return 0;
157 }
158