codeforces 27 E. Number With The Given Amount Of Divisors (dfs,反素数(假))

题目链接

题意:求约数个数恰好为n个的最小的x

思路:这道题是作为反素数的例题出现在acdreamer的博客里的。

但是实际上,这道题应该和反素数没有关系。

如果题目问的是最小的约数个数大于等于n的x,那么答案一定是反素数…打表就行了。。。

但是问的是恰好,比如如果n为5,那么最小的x是16,但是x不是反素数。

所以其实就是个dfs啦。

理论依据是:

一个数 A 可以分解成 p1k1 * p2k2 * …… * pnkn 其中p为素数。这样分解之后,A的因子个数

S = (k1+1) *( k2+1) * …… *( kn+1)

 

以及要找的是一个最小的x,满足约数个数等于n。

那么关于反素数的两个性质依然是满足的:

(1)一个反素数的所有质因子必然是从2开始的连续若干个质数,因为反素数是保证约数个数为的这个数尽量小

(2)同样的道理,如果,那么必有

 

 

 

 

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz