集训队作业解题报告

1、题目来源Ural 1586 Threeprime Numberhttp:/acm.timus.ru/problem.aspx?space=1&num=1586问题描述 输出有多少n位整数，其中任意连续三位数字都组成三位数的素数（不首0）。答案模1000000009输出。核心算法 先枚举所有三位质数。递推ai,j,k前i位满足条件，末两位j,k，的方案数。递推方程：ai,j,k=。算法证明 无需证明。算法实现 没有实现上的困难。源代码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