poj 2886 Who Gets the Most Candies? (线段树模拟加强版约瑟夫问题+反素数)

poj 2886 题目链接

题意:n个人围成一圈,每个人身上由一个数,可正可负。从第k个人开始出圈,如果第k个人身上的数是X,X>0,就左边第x个没有出圈的人出圈,否则右边第-X个人出圈。 第k个人出圈得到的糖果数目为f(k),f(x)表示x的因子个数。现在问谁能拿到最多的糖果,并且拿到了多少糖果。

思路:看起来好像很麻烦。。其实可以分解成两个问题。

第一个子问题就是约瑟夫问题的加强版。。。每次间隔不是定数,而取决与上一次出队的人。。。

终点是数据有5E5.。。模拟的话会炸掉。。。所以用线段树来模拟这个过程。。。

类似于那道插队的问题。。。线段树的域存的是某区间中空位置的数量。。初始为1.。。

然后每次update的时候优先查看左子树。。。

第二个子问题就是。。。到底第几个出去的人那道的糖果最多。。。。

其实也就是求1..n中。。。因子数最大的那个。。。

利用反素数表。。。每次upper_bound一下即可。。。

 

顺便再来个打反素数以及对应约数的表。

 

 

bzoj 1053: [HAOI2007]反素数ant

 

1053: [HAOI2007]反素数ant

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 2750  Solved: 1559
[Submit][Status][Discuss]

Description

  对于任何正整数x,其约数的个数记作g(x)。例如g(1)=1、g(6)=4。如果某个正整数x满足:g(x)>g(i) 0<i<x
,则称x为反质数。例如,整数1,2,4,6等都是反质数。现在给定一个数N,你能求出不超过N的最大的反质数么

Input

  一个数N(1<=N<=2,000,000,000)。

Output

  不超过N的最大的反质数。

Sample Input

1000

Sample Output

840

HINT

Source

 

 

思路:dfs然后剪一下。。。和ural 1748同样的做法。。。。

还可以。。。打表。。。。

有表不打和咸鱼有什么区别呢

(oi赛制不可以带纸质材料,所以打表大概算是恶习…不过acm不一样啊orz。。。反素数表1..1E18也才167个。。。。

 

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)同样的道理,如果,那么必有

 

 

 

 

 

 

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个):

 

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

 

反素数学习笔记

acdreamer的博客

wiki上的反素数是什么鬼orz…完全不是一个东西吧。。。。

反素数直观得理解。。。就是一个约数特别多的数。。。因为素数的约数最少。。。所以约数多的数就叫反素数(?随便口胡的…

由于1E18之前的反素数大概只有167个。。。所以打表可以很方便。。。

反素数是第一个约数“增长”到某个数的数,必须是“增长”,而不是第一个约数个数为某个数的数。

因为16是第一个约数个数为5的个数,但是16不是反素数,因为比16小的12有6的约数。。。

反素数的两个性质非常好用。。。

一个是反素数分解的质因子一定是连续的。。。

另一个是反素数分解的质因子的指数一定不增。。。

这两个性质都很显然。。。。证明没啥必要。。。

这两个性质可以用来dfs的时候剪枝。。。