hdu 2521 反素数

题目链接

题意:求区间[a,b]中约数最多的那个数,如果有多个,输出最小的。

思路:看起来好像和反素数没什么关系…只是打个约数个数的表…

但是实际上,所有的答案恰好都是反素数。。。

我们回顾反素数的定义:设f(x)为x的约数个数,那么如果f(n)>f(i) (0<i<n),n就被称为反素数.

换句话说,对于所有f(x)==k的x组成的集合,最小的那个x就是反素数。

需要注意的是,因数个数并不单调。。因此上面那句话并不准确。。。

举个例子,16虽然有5个因子,是第一个有5个因子的数,但是16不是反素数,因为比16小的12有6个因子。

 

那么这个东西有什么用呢。。。。

我们发现。。。反素数的分布很稀疏。。。因此。。。可以直接打表。。。

一张反素数的表(一共167个):

 

当然这道题数据小可以直接打因数个数的表…

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz