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 |
解题思路得到前i个元素{v1,v2,...,vi}后,求第i+1个元素v(i+1)。 (1) vi分解出质因数{p0,p1,p2,...},v(i+1)一定是{p0,p1,p2,...}中某个质数的整倍数。 (2) 逐个求出{p0,p1,p2,...}中每个质数在{v1,v2,...,vi}里未出现过的最小倍数,v(i+1)即这些最小倍数里的最小值。 (3) 由于100万以内的质数是有限的,所以第2步中求质因数的最小未出现过倍数,每个质数的搜索起点可以全局记下来更新。 最后,对100万以内每个数字分解质因数需要一开始一把做好,否则要超时。 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator