集訓(xùn)隊(duì)作業(yè)解題報(bào)告

1、題目來源Ural 1586 Threeprime Numberhttp:/acm.timus.ru/problem.aspx?space=1&num=1586問題描述 輸出有多少n位整數(shù)，其中任意連續(xù)三位數(shù)字都組成三位數(shù)的素?cái)?shù)（不首0）。答案模1000000009輸出。核心算法 先枚舉所有三位質(zhì)數(shù)。遞推ai,j,k前i位滿足條件，末兩位j,k，的方案數(shù)。遞推方程：ai,j,k=。算法證明 無需證明。算法實(shí)現(xiàn) 沒有實(shí)現(xiàn)上的困難。源代碼const pp=1000000009;var p:array1.1000of boolean; a,b:array1.1000of longint; i,j,n,

2、k,ans:longint;function prime(x:longint):boolean;var i:longint;begin for i:=2 to round(sqrt(x)+1) do if x mod i=0 then exit(false); prime:=true;end;begin for i:=101 to 997 do pi:=prime(i); for i:=100 to 997 do if pi then ai:=1 else ai:=0; readln(n); for j:=4 to n do begin fillchar(b,sizeof(b),0); for

3、 i:=101 to 997 do if pi then begin k:=(i mod 100)*10; if pk+1 then bk+1:=(bk+1+ai)mod pp; if pk+3 then bk+3:=(bk+3+ai)mod pp; if pk+7 then bk+7:=(bk+7+ai)mod pp; if pk+9 then bk+9:=(bk+9+ai)mod pp; end; a:=b; end; ans:=0; for i:=101 to 997 do ans:=(ans+ai)mod pp; writeln(ans);end.原題描述：1586. Threepri

4、me NumbersTime Limit: 1.0 secondMemory Limit: 64 MBRest at the sea is wonderful! However, programmer Pasha became awfully bored of lying on a beach in Turkey; so bored that he decided to count the quantity of three-digit prime numbers. This turned out to be so interesting that he then started to stu

5、dy threeprime numbers. Pasha calls an integer a threeprime number if any three consecutive digits of this integer form a three-digit prime number. Pasha had already started working on the theory of the divine origin of such numbers when some vandals poured water on Pasha and cried some incomprehensi

6、ble words like “Sonnenstich!”, “Colpo di sole!”, and “Coup de soleil!” You are to continue Pashas work and find out how often (or rare) threeprime numbers are. InputThe input contains an integer n (3 n 10000). OutputOutput the quantity of n-digit threeprime numbers calculated modulo 109 + 9. Sampleinputoutput4204Problem Author: Denis M