發表新討論
#7336: 心得分享 (劇透


uko (TJ)

d934. F. Lisa 的圍巾 -- 2010 NPSC 國中組初賽 | From: [111.254.239.28] | 發表日期: 2012-12-23 20:42
看到這題是國中生初賽 囧 現在國中生好強
我是用DP解的，首先建一個表，A(1)~A(7000)，A(n)表示從1到n的非質數合
然後算出A(a)跟A(b)的差就能得到a~b的非質數合
建表的方法如下: 
A(1)=1 
for i:=2~7000
    if(i是質數)
        Ai=A(i-1)
    else
        Ai=i+A(i-1)
求解的方法如下:
print A(b)-A(a-1) 
ZeroJudge Forum