2021常州市程序设计小能手比赛试题
需积分: 5 75 浏览量
2023-05-06
15:39:52
上传
评论
收藏 538KB PDF 举报
2021 年常州市“程序设计小能手”比赛说明
在 D 盘根目录下建一个以自己的中文名字命名的文件夹如“丁宁”，活动结束
前将你编的所有程序(扩展名为 cpp)放到该文件夹中，然后右击该文件夹在
弹出菜单中选择“添加到丁宁.rar”，压缩后等待工作人员上传到教师机。
一般说来前面的题要比后面的容易，后面的题目虽然得到满分很难，然而拿
一部分分数并不难。请合理分配你的时间，先保证程序的正确性，超时等问
题都是次要的，计算机的运行速度往往比你想象的要快得多。如果某题不太
会做你可以针对小数据编程争取拿部分分数，哪怕手算一个结果输出也行，
比赛总是有难度的，不能像平时学校里的小测验那样老想着拿满分，从往年
的经验来看你能得到总分的 1/4 就相当不错了。
所有测试点时限都是 1 秒，所有程序运行时内存都不能超过 256MB，大约可
以存储六千万个 int 类型的整数。
输出时行首和行尾都不要有多余的空格，也不要有多余的空行，相邻两项输
出之间严格用一个空格隔开，一行输出结束时一定要换行。
程序名在题目后面的括号中，千万不能起错名字。所有题目均使用标准输入
输出，即从键盘输入数据，结果输出到屏幕，请认真阅读范例，你的程序请
严格按范例程序的格式编写。
编译不打开任何优化开关，包括但不限于 c++11 和 O2。
题目中用到的“∧”符号表示乘方运算，如 2^3=2×2×2=8，10^6=1000000。
【范例】
最大公约数和最小公倍数(gcdlcm.cpp)
问题描述
最大公约数(Greatest Common Divisor，简写为 GCD)：如果有一个自然数 a 能被自然
数 b 整除(也称 b 能整除 a，记作 b|a)，则称 a 为 b 的倍数，b 为 a 的约数。两个自然数公
共的约数，叫做这两个自然数的公约数。所有公约数中最大的一个，称为这两个自然数的最
大公约数。最小公倍数(Least Common Multiple，缩写 LCM)：对于两个自然数来说，最
小公倍数是指这两个数公共的倍数中最小的一个。例如： 在 12 和 16 中，4 就是 12 和 16
的最大公约数。12 和 16 的最小公倍数是 48。
早在公元前 300 年左右，欧几里德就在他的著作《几何原本》中给出了求最小公倍数
的高效方法——辗转相除法。辗转相除法使用到的原理很聪明也很简单，假设用 GCD(x, y)
表示两个自然数 x 与 y 的最大公约数，取 k = x / y，b = x % y，则 x = k * y + b，如果一个
自然数能够同时整除 x 和 y，则必能同时整除 b 和 y；而能够同时整除 b 和 y 的自然数也必
能同时整除 x 和 y，即 x 和 y 的公约数与 b 和 y 的公约数是相同的，其最大公约数当然也
剩余12页未读，继续阅读
资源评论
