因数（factor）

一个最基本的算数法则就是大于1的整数都能用1个或多个素数相乘的形式表示出来。当然，有多种质因子排列方案

如：

10=2×5=5×2 20=5×2×2=2×5×2=2×2×5

用f(k)表示k的质因数排列数，f(10)=2,f(20)=3

给一个n，至少有一个k满足f(k)=n的最小k

输出格式：n和k

输入：

105

输出：

1 2

2 6

3 12

105 720

数据范围

n，k<2^63

我们令k=∏pi^ei

S=∑ei

f(k)=S!/(∏ei!)

解释一下：S是所有因数的个数，ei是每一种因数的个数

显然不考虑重复的情况时方案为S！

那么算上重复的会怎样？

1112是已定的

如果是算总方案显然4！，那么111会导致的重复方案是3！2导致的重复方案为1！

所以有了以上结论

那么我们有了一种方法：枚举k得到n

显然不行

那么是否可以试一下已知n，得到k？

已知对于一个指数e，如果在可行条件下，那么它显然优先给最小的质因数，这能导致k最小

搜索+剪枝实现

剪枝1：上面说的优先给小的素数，就是说ei要单调递增，因为如果ei>ej,i>j,那么显然把ei与ej

交换才能最优

剪枝2：假设你每举了t素数的指数e

就要把n除以 ((S-e+1)*…*S) /e!

如何高效算出?

原式=>S!/(e!*(S-e)!)

这不就是C(S,S-e)吗？

预处理出C，然后每一层枚举一个素数的指数，然后向下

剪枝3：最优性剪枝，当前k>ans 则退出

预处理幂不说了

但记住无论是幂，还是k，都不能超过(1<<63)-1

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 int pr[15]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
 7 long long pw[15][64],C[64][64],ans;
 8 long long inf;
 9 long long min(long long a,long long b)
10 {
11   if (a<b) return a;
12   else return b;
13 }
14 void dfs(int t,long long now,long long pre,long long s,int down)
15 {
16   if (s>ans) return;
17   if (now==1)
18     {
19       ans=min(ans,s);
20       return;
21     }
22   if (t>14) return;
23   for (int i=pre+1;i<=min(pre+down,62);i++)
24     if (now%C[i][i-pre]==0&&pw[t][i-pre]&&s<=inf/pw[t][i-pre])
25       dfs(t+1,now/C[i][i-pre],i,s*pw[t][i-pre],i-pre);
26 }
27 void ask_ans(long long k)
28 {
29   ans=inf;
30   dfs(0,k,0,1,62);
31   ans=max(ans,2);
32 }
33 int main()
34 {int i,j,k;
35   freopen("factor.in","r",stdin);
36   freopen("factor.out","w",stdout);
37   C[0][0]=1;
38   for (i=1;i<64;i++)
39     {
40       C[i][0]=C[i][i]=1;
41       for (j=1;j<i;j++)
42         C[i][j]=C[i-1][j-1]+C[i-1][j];
43     }
44   for (i=0;i<=14;i++)
45     {
46       pw[i][0]=1;
47       for (j=1;j<=63;j++)
48     {
49       if (i&&pw[i][j-1]>inf/pr[i]) break;
50       pw[i][j]=pw[i][j-1]*pr[i];
51     }
52       if (i==0)
53     inf=pw[0][63]-1;
54     }
55   while (cin>>k)
56     {
57       ask_ans(k);
58       cout<<k<<' '<<ans<<endl;
59     }
60 }