哥德巴赫分解

题目描述

哥德巴赫猜想认为：不小于4的偶数都可以表示为两个素数的和。

你不需要去证明这个定理，但可以通过计算机对有限数量的偶数进行分解，验证是否可行。

实际上，一般一个偶数会有多种不同的分解方案，我们关心包含较小素数的那个方案。

对于给定数值范围，我们想知道这些包含较小素数方案中最大的素数是多少。

比如，100以内，这个数是19，它由98的分解贡献。

你需要求的是10000以内，这个数是多少？

数组操作

题目描述

给出一个长度为 n 的数组 {A}，由 1 到 n 标号 ， 你需要维护 m 个操作。

操作分为三种，输入格式为：

1 L R d，将数组中下标 L 到 R 的位置都加上 d，即对于 L<=i<=R，执行A[i]=A[i]+d。

2 L1 R1 L2 R2，将数组中下标为 L1 到 R1 的位置，赋值成 L2 到 R2 的值，保证 R1-L1=R2-L2。

换句话说先对 0<=i<=R2-L2 执行 B[i]=A[L2+i]，再对 0<=i<=R1-L1 执行 A[L1+i]=B[i]，其中 {B} 为一个临时数组。

3 L R，求数组中下标 L 到 R 的位置的和，即求出 $∑_(i=L到R) A_i $。

输入格式

从标准输入读入数据。

第一行一个整数 Case，表示测试点编号，其中 Case=0 表示该点为样例。

第二行包含两个整数 n,m。保证 \(1<=n,m<=10^5\)。

第三行包含 n 个整数 \(A_i\)，表示这个数组的初值。保证 \(0<=A_i<=10^5\)。

接下来 m 每行描述一个操作，格式如问题描述所示。

对于操作中提到每个数，满足 0<=d<=10^5，1<=L<=R<=n，1<=L1<=R1<=n，1<=L2<=R2<=n，R1-L1=R2-L2。

输出格式

输出到标准输出。

对于每次 3 操作输出一行一个数，表示求和的结果。

样例输入

0

5 6

1 2 3 4 5

2 1 3 3 5

3 3 5

1 2 4 2

3 3 5

2 1 3 3 5

3 1 5

样例输出

14

18

29

数字划分

题目描述

w星球的长老交给小明一个任务：

1, 2, 3… 16 这16个数字分为两组。

要求：

1、这两组数字的和相同，

2、并且，两组数字的平方和也相同，

3、并且，两组数字的立方和也相同。

请你利用计算机的强大搜索能力解决这个问题。

并提交1所在的那个分组的所有数字。

这些数字要从小到大排列，两个数字间用一个空格分开。

即类似：1 4 5 8 … 这样的答案。

笨笨有话说：只要一个组的成员确定了，另一个组的成员也就确定了。枚举一个组的成员就可以了。凭直觉，两个组的成员数目不会差太多吧。

歪歪有话说：既然求 1 所在的那个组，那只要枚举剩余的成员就可以了。貌似都是8个成员的可能性很大啊。

答案提交

注意，只提交这一组数字，不要填写任何多余的内容。

分考场

题目描述

n个人参加某项特殊考试。

为了公平，要求任何两个认识的人不能分在同一个考场。

求最少需要分几个考场才能满足条件。

输入格式：

第一行，一个整数n(1<n<100)，表示参加考试的人数。

第二行，一个整数m，表示接下来有m行数据

以下m行每行的格式为：两个整数a，b，用空格分开 (1<=a,b<=n) 表示第a个人与第b个人认识（编号从1开始）。

输出格式：

一行一个整数，表示最少分几个考场。

例如：

输入：

5

8

1 2

1 3

1 4

2 3

2 4

2 5

3 4

4 5

程序应该输出：

4

再比如：

输入：

5

10

1 2

1 3

1 4

1 5

2 3

2 4

2 5

3 4

3 5

4 5

则程序应该输出：

5

资源约定：

峰值内存消耗 < 256M

CPU消耗 < 1000ms

小数第n位

题目描述

我们知道，整数做除法时，有时得到有限小数，有时得到无限循环小数。

如果我们把有限小数的末尾加上无限多个0，它们就有了统一的形式。

本题的任务是：在上面的约定下，求整数除法小数点后的第n位开始的3位数。

输入：

一行三个整数：a b n，用空格分开。a是被除数，b是除数，n是所求的小数后位置（0<a,b,n<1000000000）

输出：

一行3位数字，表示：a除以b，小数后第n位开始的3位数字。

比如：

输入：

1 8 1

程序应该输出：

125

再比如：

输入：

1 8 3

程序应该输出：

500

再比如：

输入：

282866 999000 6

程序应该输出：

914

提交时，注意选择所期望的编译器类型。

合根植物

题目描述

w星球的一个种植园，被分成 m * n 个小格子（东西方向 m 行，南北方向 n 列），每个格子里种了一株合根植物。

这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。

如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？

输入格式

第一行，两个整数m，n，用空格分开，表示格子的行数、列数（1 < m, n < 1000）。

接下来一行，一个整数 k，表示下面还有 k 行数据(0 < k < 100000)

接下来 k 行，第行两个整数 a，b，表示编号为 a 的小格子和编号为 b 的小格子合根了。

格子的编号一行一行，从上到下，从左到右编号。

比如：5 * 4 的小格子，编号：

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15 16

17 18 19 20

样例输入

5 4

16

2 3

1 5

5 9

4 8

7 8

9 10

10 11

11 12

10 14

12 16

14 18

17 18

15 19

19 20

9 13

13 17

样例输出

5

样例解释