反素数

反素数

对于任何正整数$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);