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的约数。。。 反素数的两个性质非常好用。。。 一个是反素数分解的质因子一定是连续的。。。 另一个是反素数分解的质因子的指数一定不增。。。 这两个性质都很显然。。。。证明没啥必要。。。 这 …

题目链接 题意：n只青蛙，第i只位于x[i],舌头长度为t[i]。m只蚊子，第i只蚊子所在位置为p[i],蚊子的大小为b[i]。 蚊子按照出现顺序输入。 一只青蛙能吃到蚊子当且仅当蚊子和青蛙在同一个位置，或者蚊子在青蛙右边并且与青蛙的距离小于等于该青蛙舌头的长度。 当多只青蛙可以吃到同一只蚊子的时候，最左边的那只青蛙来吃。 当一只青蛙吃掉一只蚊子以后，青蛙的舌头增加蚊子的大小。 当一只青蛙吃掉一只蚊子后，因为舌头边长而又能吃到其他蚊子的时候，这只青蛙会继续吃，只到当前没有蚊子可以被任何一只青蛙吃到，在这个过程之后才会飞来下一只蚊子。 思路：问题的关键在于，对于某只蚊子，我们如何找到能吃到该蚊子的青蛙中最左边的那只。 可以抽象成寻找区 …

题目链接 题意：一个无穷数列，从1开始，初始第i个位置上为i，给出n个swap，每次交换两个位置的数。问交换n次以后得到的数列中，逆序对的数。 思路： 官方题解： At first find the position of each element which is used in swap (using map). Now let's find the answer. It consists of the two parts. First part is the number of inversions formed by only whose elements which took part in the swaps. They …

题意：给出n个数，两两做差的绝对值，共有m=n*(n-1)/2个，问其中的中位数是多少。特别地，当m为偶数的时候，中位数为第m/2个。 思路：二分中位数。 一开始还觉得由于中位数在整数意义上不连续不能二分。。。。 但是最后结果不可能是那样的答案啊。。。 check的条件是，以k为中位数的时候，绝对值小于k的数要小于(m+1)/2个（也就是中位数所在的位置） check的时候尺取即可。 复杂度 排序O(nlgn) + 二分(lgn)*尺取O(n) ，整体O(nlgn) /* *********************************************** Author :111qqz Created Time :Tue …

题目链接 题意：给出n个x轴上的坐标点，选取其中c个，问c个之中任意两个点的最小距离最大是多少。 思路：二分距离check合法性。 大水题。。。因为想把三分艹掉。。。三分的题又多和二分挂在一起。。。顺便就写了。。。。 /* *********************************************** Author :111qqz Created Time :Mon 19 Sep 2016 10:57:54 PM CST File Name :code/poj/2456.cpp ************************************************ */ #include …

题目链接 题意：圆上，询问任意一段弧中，任意两点的距离+两点的权值和的最大值。 思路： 1.环先拆成串，复制1..n到后面，变成1..2n。 化简公式： 2 * h[u] + 2 * h[v] + dist(u, v) = 2 * h[v] + d[1] + d[2] + ... + d[v-1] + 2 * h[u] - (d[1] + d[2] + ... + d[u-1]). 设A[v] = 2 * h[v] + d[1] + d[2] + ... + d[v-1], B[u] = 2 * h[u] - (d[1] + d[2] + ... + d[u-1]). Another important thing is that …

题目链接 题意：有n个数，每次可以删除掉数值相同并且所在位置成等差数列（只删2个数或者只删1个数应该也是可以的），删掉这些数以后可以将剩下的数重新以任意顺序排列，称为一次操作。现在给出m个询问，每个询问一个区间[l,r]，问删光区间[l,r]中的数最少需要的操作次数。 思路/题解：由于第一次操作之后可以重排，那么把相同的数放在一起得到一个位置的公差为1的等差数列，之后的答案显然是元素个数。所以需要判断初始的时候，是否能一次删光某个数值的数，也就是需要判断初始时刻是否有某个数出现的所有位置组成一个等差数列。 (去icpc-camp的论坛问了一波。。。链接在这里) 之前刚刚学了判断一个区间中不同的数有多少个的姿势。。。 所以问题就在于如 …