第1~10题为基础题，第11~20题为提高题，第21~33为综合题
注：因为在本文档中需要用到一些特殊的数学符号（如：求和号、分数等），所以当您在百度文库中浏览时，一些数学符号可能会显示不出来，不过当您把本文档下载下来在本地浏览时，所有的符号即可全部都显示出来。^_^
基础题：
【1 Prime Frequency】
【问题描述】
给出一个仅包含字母和数字（0-9, A-Z 以及 a-z）的字符串，请您计算频率（字符出现的次数），并仅报告哪些字符的频率是素数。
输入：
输入的第一行给出一个整数T ( 0<T<201)，表示测试用例个数。后面的T行每行给出一个测试用例：一个字母-数字组成的字符串。字符串的长度是小于2001的一个正整数。
输出：
对输入的每个测试用例输出一行，给出一个输出序列号，然后给出在输入的字符串中频率是素数的字符。这些字符按字母升序排列。所谓“字母升序”意谓按ASCII 值升序排列。如果没有字符的频率是素数，输出“empty”（没有引号）。
样例输入
样例输出字符串长度在线测试
3
ABCC
AABBBBDDDDD
ABCDFFFF
Case 1: C
Case 2: AD
Case 3: empty
注：
  试题来源：Bangladesh National Computer Programming Contest
在线测试：UVA 10789
提示
  先离线计算出[2‥2200]的素数筛u[]。然后每输入一个测试串，以ASCLL码为下标统计各字符的频率p[]，并按照ASCLL码递增的顺序（0≤i≤299）输出频率为素数的字符（即u[p[i]]=1且ASCLL码值为i的字符）。若没有频率为素数的字符，则输出失败信息。
【2 Twin Primes】
【问题描述】 
双素数（Twin Primes）是形式为(p, p+2)，术语“双素数”由Paul Stäckel (1892-1919)给出，前几个双素数是(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43)。在本题中请你给出第S对双素数，其中S 是输入中给出的整数。
输入：
输入小于10001行，每行给出一个整数S (1≤ S≤ 100000)，表示双素数对的序列编号。输入以EOF结束。
输出：
对于输入的每一行，输出一行，给出第S对双素数。输出对的形式为(p1,空格p2)，其中“空格”是空格字符(ASCII 32)。本题设定第100000对的素数小于20000000。
样例输入
样例输出
1
2
3
4
(3, 5)
(5, 7)
(11, 13)
(17, 19)
注：
  试题来源：Regionals Warmup Contest 2002, Venue: Southeast University, Dhaka, Bangladesh
在线测试：UVA 10394
提示
设双素数对序列为ans[]。其中ans[i]存储第i对双素数的较小素数（1≤i≤num）。ans[]的计算方法如下：
使用筛选法计算出[2，20000000]的素数筛u[]；
按递增顺序枚举该区间的每个整数i：若i和i+2为双素数对（u[i]&&u[i+2]）,则双素数对序列增加一个元素（ans[++num]=i）。
在离线计算出ans[]的基础上，每输入一个编号s，则代表的双素数对为(ans[s]，ans[s]+2)。
【3 Less Prime】
【问题描述】
设n为一个整数，100≤n≤10000，请到素数x，x ≤ n，使得n-p*x最大，其中 p是整数，使得p*x≤n<(p+1)*x。
输入:
输入的第一行给出一个整数M，表示测试用例的个数。每个测试用例一行，给出一个整数N，100≤N≤10000。
输出:
对每个测试用例，输出一行，给出满足上述条件的素数。
样例输入
样例输出
5
4399
614
8201
101
7048
2203
311
4111
53
3527
注：
  试题来源：III Local Contest in Murcia 2005
在线测试：UVA 10852
提示
要使得n-p*x最大（x为素数，p为整数，p*x ≤ n<(p+1)*x），则x为所有小于n的素数中，被n除后余数最大的一个素数。由此得出算法：
先离线计算出[2‥11111]的素数表su[]，表长为num。然后每输入一个整数n，则枚举小于n的所有素数，计算tmp=，满足条件的素数即为对应tmp=n%su[k]的素数su[k]。
【4 Prime Words】
【问题描述】
一个素数是仅有两个约数的数：其本身和数字1。例如，1, 2, 3, 5, 17, 101和10007是素数。
本题输入一个单词集合，每个单词由a-z以及A-Z的字母组成。每个字母对应一个特定的值，字母a对应1，字母b对应2，以此类推，字母z对应26；同样，字母A对应27，字母B对应28，字母Z对应52。
一个单词的字母的总和是素数，则这个单词是素单词（prime word）。请编写程序，判定一个单词是否为素单词。
输入：
输入给出一个单词集合，每个单词一行，有L个字母，1≤L≤20。输入以EOF结束。
输出：
如果一个单词字母的和为素数，则输出“It is a prime word.”；否则输出“It is not a prime word.”。
样例输入
样例输出
UFRN
contest
AcM
It is a prime word.
It is not a prime word.
It is not a prime word.
注：
  试题来源：UFRN-2005 Contest 1
在线测试：UVA 10924
提示
由于字母对应数字的上限为52，而单词的长度上限为20，因此我们首先使用筛选法，离线计算出[2‥1010]的素数素数筛u[]。
然后每输入一个长度为n的单词，计算单词字母对应的数字和
X=
若x为[2‥1010]中的一个素数（u[x]=1），则表明该单词为素单词；否则该单词非素单词。
【5 Sum of Different Primes】
【问题描述】
一个正整数可以以一种或多种方式表示为不同素数的总和。给出两个正整数n和k，请您计算将n 表示为k个不同的素数的和会有几种形式。如果是相同的素数集，则被认为是相同的。例如8可以被表示为3 + 5和5 + 3，但不区分。
如果n和k分别为24和3，答案为2，因为有两个总和为24的集合 {2, 3, 19}和{2, 5, 17} ，但不存在其他的总和为24的3个素数的集合。如果n = 24，k = 2，答案是3，因为存在3个集合{5, 19}, {7, 17}以及{11, 13}。如果n = 2，k = 1，答案是1，因为只有一个集合{2} ，其总和为2。如果n = 1，k = 1，答案是0，因为1不是素数，不能将{1}计入。如果n = 4，k = 2，答案是0，因为不存在两个不同素数的集合，总和为4。
请您编写一个程序，对给出的n和k，输出答案。
输入：
输入由一系列的测试用例组成，最后以一个空格分开的两个0结束。每个测试用例一行，给出以一个空格分开的两个正整数n和k。本题设定n ≤ 1120，k ≤ 14。
输出：
输出由若干行组成，每行对应一个测试用例，一个输出行给出一个非负整数，表示对相应输入中给出的n和k有多少答案。本题设定答案小于231。
样例输入
样例输出
24 3
24 2
2 1
1 1
4 2
18 3
17 1
17 3
17 4
100 5
1000 10
1120 14
0 0
2
3
1
0
0
2
1
0
1
55
200102899
2079324314
注：
试题来源：ACM Japan 2006
在线测试：POJ 3132，ZOJ 2822，UVA 3619
提示
设
  su[]为[2..1200]的素数表；f[i][j]为j拆分成i个素数和的方案数(1≤i≤14, su[i]≤j≤1199)。显然，边界值f[0][0]=1。
首先，采用筛选法计算素数表su[]，表长为num。然后每输入一对n和k，使用动态规划方法计算k个不同素数的和为n的方案总数：
枚举su[]表中的每个素数su[i](1≤i≤num）
  按递减顺序枚举素数个数j(j=14‥1)：
    按递减顺序枚举前j个素数的和p（p=1199‥su[i]）:
累计su[i]作为第j个素数的方案总数f[j][p]+=f[j-1][p-su[i]];

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。