Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:我的做法,希望对大家有帮助。

Posted by sdfzfzq at 2015-11-21 15:39:36 on Problem 2886
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator