Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:我的做法,希望对大家有帮助。In Reply To:我的做法,希望对大家有帮助。 Posted by:noisy at 2009-07-04 17:12:05 > 首先预处理反素数: > 什么是反素数呢?就是说对于一个反素数n,那么从1...n里面所有的数中,n的约数个数是最多的。例如4,6就是反素数。 > 那么预先处理一下(或着打表),因为最大不超过500000,而且找反素数有个性质: > 性质一:一个反素数的质因子必然是从2开始连续的质数. > 因为最多只需要7个素数构造:2,3,5,7,11,13,17(2*3*5*7*11*13*17>500000) > 性质二:p=2^t1*3^t2*5^t3*7^t4.....必然t1>=t2>=t3>=.... > 所以给出一个反素数p=2^t1*3^t2*5^t3*7^t4....,那么它的约数个数就是(t1+1)*(t2+1)*... > 所以这里用个递归将所有小于n,的最大反素数找出来。 > 接下来就比较容易做,都是线段树的内容。假设当前位置为k,要移动m,而且还没删除当前点的时候有n个人,那么: > 如果m>0,那么k=((k-1+m)%(n-1)+n-1)%(n-1); > m<0那么k=((k+m)%(n-1)+n-1)%(n-1);(请注意和上面那个的区别) > 然后找当前线段树里面第k个还没走的人,并记录他的名字,做g(n)次(g(n)是指小于等于 n的最大反素数)。 > > Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator