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

解题思路

Posted by aoxboxcox at 2021-11-16 15:13:49 on Problem 1619
得到前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:
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