2020年常州市“程序设计小能手”比赛说明

u 在D盘根目录下建一个以自己的中文名字命名的文件夹如“丁宁”，活动结束前将你编的所有程序(扩展名为cpp)放到该文件夹中等待工作人员上传到教师机。

u 一般说来前面的题要比后面的容易，后面的题目虽然得到满分很难，然而拿一部分分数并不难。请合理分配你的时间，先保证程序的正确性，超时等问题都是次要的，计算机的运行速度往往比你想象的要快得多。如果某题不太会做你可以针对小数据编程争取拿部分分数，哪怕手算一个结果输出也行，比赛总是有难度的，不能像平时学校里的小测验那样老想着拿满分，从往年的经验来看你能得到总分的1/4就相当不错了。

u 所有测试点时限都是1秒，所有程序运行时内存都不能超过256MB，大约可以存储六千万个长整型数。每题一般有10以上测试点，除非特别说明，每题的分值均为100分。每题的分值必定是测试点总数的倍数。

u 输出时行首和行尾都不要有多余的空格，也不要有多余的空行，相邻两项输出之间严格用一个空格隔开，一行输出结束时一定要换行。

u 程序名在题目后面的括号中，千万不能起错名字。所有题目均使用标准输入输出，即从键盘输入数据，结果输出到屏幕，请认真阅读范例，你的程序请严格按范例程序的格式编写。

u 题目中用到的“∧”符号表示乘方运算，如2^3=2*2*2=8，10^6=1000000

u 小学组题数和难度参照往年本比赛。初中组题数和难度参照CSP入门组。

【范例】最大公约数和最小公倍数(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 div y，b = x mod y，则x = ky + b，如果一个数能够同时整除x和y，则必能同时整除b和y；而能够同时整除b和y的数也必能同时整除x和y，即x和y的公约数与b和y的公约数是相同的，其最大公约数当然也相同，则当y<>0时有GCD(x, y)= GCD(y, x mod y)，如此便可把原问题转化为求两个更小数的最大公约数，直到其中一个数为0，剩下的另外一个数就是两者的最大公约数。以求288和123的最大公约数为例，操作如下： 　　288 mod 123=42 　　123 mod 42=39 　　42 mod 39=3 　　39 mod 3=0 　　所以3就是288和123的最大公约数。

计算最小公倍数时，通常会借助最大公约数来辅助计算。可以证明两个自然数的乘积等于它们的最大公约数和最小公倍数的乘积，即a*b=GCD(a,b)*LCM(a,b)。如12*16=192= GCD(12,16)*LCM(12,16)=4*48。

编一个程序对于输入的两个自然数a,b，求它们的最大公约数和最小公倍数。

输入格式

输入数据仅有一行包含两个用空格隔开的正整数a,b，范围不超过长整型longint。

样例输入

12 16

输出格式

输出数据仅有一行包含两个整数，表示要求的最大公约数和最小公倍数。两数之间严格用一个空格隔开，行末没有多余的空格。

样例输出

4 48

以下是C++源程序，存盘文件名为gcdlcm.cpp

#include <bits/stdc++.h>

using namespace std;

int main(){

Long long m,n,a,b,r;

cin>>m>>n;

a=m;

b=n;

while (b!=0){

r=a%b;

a=b;

b=r;

}

cout<<a<<" "<<m*n/a<<endl;

return 0;

}