NOIP2014普及组复赛C++题解：珠心算测验与比例简化

"这是关于NOIP2014普及组复赛C++试题的讲解资料，包含两道题目——‘珠心算测验’和‘比例简化’的解析及示例程序。" 首先，我们来详细讲解第一题，“珠心算测验”。这是一道考察算法和效率的问题，要求计算一个正整数集合中，有多少个数可以通过集合中的另外两个不同的数相加得到。解题的关键在于正确理解题意，并采用有效的编程策略。 在解题过程中，通常采用三重循环的方法来实现。外层循环用来枚举可能的和，两个内层循环分别遍历集合中的两个数，检查它们的和是否等于外层循环的值。一旦找到一对满足条件的数，就更新答案（ans）并跳出两个内层循环，避免重复计数。需要注意的是，题目强调是“不同的”数之和，因此在内层循环中需要确保两个数不相等。 参考的C++程序展示了如何实现这个逻辑。首先，读入集合的大小（n）和每个元素，然后通过三层循环进行遍历。外层循环变量为i，代表和；内层循环变量为j和k，分别代表两个加数。在内层循环中，通过if语句判断a[i]是否等于a[j]和a[k]的和，若是则将f设置为true，表示找到了一对满足条件的数，同时增加答案ans的计数，并跳出内层循环。最后，输出答案ans。 接下来是第二题，“比例简化”。这道题涉及到比例的简化和最大公约数（GCD）的概念。目标是找到两个整数A'和B'，它们与原比例A:B保持大致相同的相对关系，同时满足A'和B'的值不超过给定的上限L，且A'和B'互质。解题时，由于L的值较小，可以直接枚举所有可能的A'和B'，寻找满足条件的最小差值。 在实现过程中，可以先计算A和B的最大公约数，然后分别用A和B除以这个公约数，得到无公约数的初始简化比例。接着，对于每一个可能的A'（从1到L），尝试找到一个对应的B'，使得A'/B'接近于A/B，并且A'和B'互质。可以使用欧几里得算法求得A'和B'的最大公约数，确保它们互质。通过遍历所有可能的A'和B'，找到最优的解决方案。 这两道题目考查了学生的算法思维、逻辑推理能力和基本的编程技巧。对于“珠心算测验”，重点在于理解问题并优化搜索空间；对于“比例简化”，则需要掌握数论中的简化比例和最大公约数的概念。通过解决这些问题，参赛者可以提升自己的编程和数学素养。