对于任何正整数$x$，其约数的个数记作$g(x)$。例如$g(1)=1、g(6)=4$。
如果某个正整数x满足：$g(x)>g(i) (0<i<x)$，则称$x$为反素数。例如，整数1，2，4，6等都是反质数。
我们知道对于$x$质因数分解，使得$x=p_1^{c_1}\times p_2^{c_2}\times\ p_k^{c_k}$
则$x$的约数个数为$(c_1+1)(c_2+1)(c_k+1)$
那么我们可以先将素数打表，dfs枚举每个素数取了几次去更新出最小值。
当然dfs的时候通过一些剪枝大大提高效率。
前15个素数均只取一次的乘积已经大于2^64，所以只要枚举前15个素数。
同时每个素数最多取的次数也不会超过64次。
贴下模板：
pos代表枚举第几个素数，value为当前的值，num为当前的约数个数，k为给出的约数个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
int prime[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,47,53};
void dfs(int pos,ll value,ll num)
{
if(num>k||pos>15) return;
if(num==k)
{
ans=min(ans,value);
return;
}
for(int i=1;i<=63;i++)
{
if(value > ans/prime[pos] || num*(i+1)>k)
break;
value=value*prime[pos];
if(k%(num*(i+1))==0) //约数个数应为k的约数
dfs(pos+1,value,num*(i+1));
}
}
dfs(0,1,1);
|