poj 2886 蜡烛
约瑟夫环+反素数  用线段树做。 反素数s的约数个数比小于它的数的约数个数都多，最大反素数就是要找到的那个得到蜡烛最多的人。此题反素数和其约数个数用打表完成，约瑟夫环用线段树完成。n是当前剩余人数，现在n中第k个人出列，他右边的第m个人（下个出列的）在剩余的n-1个人中是第（k-1+m%（n-1）)%（n-1）个,他左边第m2个人在剩余的n-1个人中是第（k+n-1-m2%（n-1））%（n-1），注意这里的（k+n-1)中的n-1不能少，否则会wa
用线段树求解是为了算出下一个人在整个数组（所有人）中的绝对编号（坐标），即把上面的相对编号转换为绝对编号。设上面2个公式算出下个人的相对位置是x，其绝对位置是整个数组中第x个没有出队的人的位置。如1，2，3，4，5，其中1，3已出队，则2是第一个未出队的人，相对位置为1，绝对位置为2.
线段树每个节点记录此段上多少个人未出队。如当前段有10个人未出队，其左子段3个，右子段7个，若相对位置为2（<=3），则继续在左子段查找，若相对位置为5（>3),则在右子段查找相对位置（5-3=2）的坐标。
查到叶节点返回它所代表的点（坐标）。
整个出队游戏在第s个人（小于等于n的最大反素数）出队时结束。打印这个人的绝对坐标对应的人名并求s的约数个数即可。

• 顶一下。。顺便水一个 POJ门常打开　开放怀抱等你 水题过就有了默契　你会爱上这里 WA和PE都是挂了　请不用客气 相约好了不过题　铁牌送给你 (0) hysramp 2008-08-06 21:06:20
  • Orz.. LS.... 送你铁牌。。 (2) kamel52045386 2008-08-06 21:08:50