宝塔服务器面板,一键全能部署及管理,送你10850元礼包,点我领取

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

如:

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

用fk)表示k的质因数排列数,f10)=2,f20)=3

给一个n,至少有一个k满足fk)=n的最小k

输出格式:n和k

输入:

1

2

3

105

输出:

1 2

2 6

3 12

105 720

数据范围

n,k<2^63

我们令k=∏piei

  S=∑ei

fk)=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)!)

这不就是CS,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 minlong long a,long long b)
10 {
11   if a<b) return a;
12   else return b;
13 }
14 void dfsint 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=minans,s);
20       return;
21     }
22   if t>14) return;
23   for int i=pre+1;i<=minpre+down,62);i++)
24     if now%C[i][i-pre]==0&&pw[t][i-pre]&&s<=inf/pw[t][i-pre])
25       dfst+1,now/C[i][i-pre],i,s*pw[t][i-pre],i-pre);
26 }
27 void ask_anslong long k)
28 {
29   ans=inf;
30   dfs0,k,0,1,62);
31   ans=maxans,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_ansk);
58       cout<<k<<' '<<ans<<endl;
59     }
60 }