noi2012试题

### NOI2012试题分析 #### 质因数分解 (prime) **问题描述**： 已知一个正整数\( n \)是两个不同质数的乘积，任务是找出这两个质数中较大的那一个。 **输入**： 输入文件名为`prime.in`，包含一个正整数\( n \)。 **输出**： 输出文件名为`prime.out`，输出一个正整数\( p \)，即较大的那个质数。 **示例**： - 输入：`217` - 输出：`31` **数据范围**： - 对于60%的数据：\( 6 \leq n \leq 1000 \) - 对于100%的数据：\( 6 \leq n \leq 2 \times 10^9 \) **算法思路**： 1. **分解质因数**：可以通过枚举的方式从小到大尝试所有可能的因子，直到找到第一个能够整除\( n \)的质数\( p \)为止。 2. **计算较大质因数**：一旦找到一个质因数\( p \)，那么另一个质因数就是\( n / p \)。需要注意的是，当\( n / p > p \)时，\( n / p \)才是较大的质因数。 #### 寻宝 (treasure) **问题描述**： 传说在一个藏宝楼中，每层楼都有若干房间，每层楼的一个房间有楼梯通向楼上。玩家需要根据每层楼房间内的指示牌上的数字来确定通向楼上的房间，最终达到顶层找到宝藏。指示牌上的数字代表从当前位置开始逆时针方向选择第几个有楼梯的房间。任务是计算从第一层到顶层所经过的所有指示牌上的数字之和，这个数字将作为打开宝藏的密钥。 **输入**： 输入文件名为`treasure.in`，包含多个整数： - 第一行包含两个整数\( N \)和\( M \)，分别表示除顶层外的楼层数和每层楼的房间数。 - 接下来\( N \times M \)行，每行包含两个整数\( x_i \)和\( y_i \)，表示第\( i \)个房间是否有楼梯（\( y_i = 1 \)表示有楼梯，\( y_i = 0 \)表示没有楼梯），以及指示牌上的数字\( x_i \)。 **输出**： 输出文件名为`treasure.out`，输出一个整数，即所有指示牌上的数字之和。 **示例**： 假设输入如下： - \( N = 2 \), \( M = 4 \) - 房间情况为：\((1, 1)\), \((2, 0)\), \((3, 1)\), \((4, 0)\), \((5, 1)\), \((6, 0)\), \((7, 1)\), \((8, 0)\) **数据范围**： - 对于所有数据：\( 1 \leq N, M \leq 100 \) **算法思路**： 1. **模拟过程**：从第一层开始，按照指示牌上的数字移动到下一个有楼梯的房间，并记录指示牌上的数字。 2. **累加密钥**：对于每一层，都需要找到通向楼上的房间，并累加该房间指示牌上的数字。 3. **到达顶层**：重复上述过程，直到达到顶层，此时累加器中的值即为打开宝藏的密钥。 以上两个题目均涉及基础算法的应用，如质因数分解中的试除法和寻宝问题中的模拟过程。通过这些练习可以帮助参赛者提升解决问题的能力以及编程技巧。