反素数
对于任何正整数$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为给出的约数个数
|
|