poj 2886 题目链接 题意：n个人围成一圈，每个人身上由一个数，可正可负。从第k个人开始出圈，如果第k个人身上的数是X,X>0，就左边第x个没有出圈的人出圈，否则右边第-X个人出圈。 第k个人出圈得到的糖果数目为f(k)，f(x)表示x的因子个数。现在问谁能拿到最多的糖果，并且拿到了多少糖果。 思路：看起来好像很麻烦。。其实可以分解成两个问题。 第一个子问题就是约瑟夫问题的加强版。。。每次间隔不是定数，而取决与上一次出队的人。。。 终点是数据有5E5.。。模拟的话会炸掉。。。所以用线段树来模拟这个过程。。。 类似于那道插队的问题。。。线段树的域存的是某区间中空位置的数量。。初始为1.。。 然后每次update的时候优先查 …

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的最大的反质数。 …

题目链接 题意：求约数个数恰好为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。 那么关于反素数的两个性质依然是满足的： …

题目链接 题意：求区间[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个因子。 那么这个东西有什么用呢。。。。 我们发现。。。反素数的分布很稀疏。。。因 …

acdreamer的博客 wiki上的反素数是什么鬼orz...完全不是一个东西吧。。。。 反素数直观得理解。。。就是一个约数特别多的数。。。因为素数的约数最少。。。所以约数多的数就叫反素数（？随便口胡的... 由于1E18之前的反素数大概只有167个。。。所以打表可以很方便。。。 反素数是第一个约数“增长”到某个数的数，必须是“增长”，而不是第一个约数个数为某个数的数。 因为16是第一个约数个数为5的个数，但是16不是反素数，因为比16小的12有6的约数。。。 反素数的两个性质非常好用。。。 一个是反素数分解的质因子一定是连续的。。。 另一个是反素数分解的质因子的指数一定不增。。。 这两个性质都很显然。。。。证明没啥必要。。。 这 …