题目标题：最大公约数和最小公倍数 题目作者：张彤彧 浙江大学
本题要求两个给定正整数的最大公约数和最小公倍数。
输入格式:
输入在一行中给出两个正整数M和N（≤1000）。
输出格式:
在一行中顺序输出M和N的最大公约数和最小公倍数，两数字间以1空格分隔。
输入样例:
511 292
输出样例:
73 2044
思路：求最大公约数的方法，目前来说最好的就是辗转相除法，也叫欧几里得算法（Euclidean Algorithm）。
例如，要计算15和24的最大公约数，首先让把较大的数赋值给p,把较小的数赋值给q，p=24,q=15;
然后计算p,q的余数，即r=p%q，显然如果r==0了，q就能整除p，从而最大公约数就是q。如果r!=0，那么可以推导出p,q的最大公因子一定等于q,r的最大公因子。
于是更新p=q,q=r, 并重复上面的步骤，直到r==0为止，这时的q就是，原p,q的最大公因子。
注意：如果p,q中有一个数是0，那么GCD(p,q)就是p,q中另一个非0的数。当然本题明确说输出都是正整数，所以不用考虑这种情况。
至于最小公倍数，它显然就是两数乘机除以最大公约数。根据上面的分析，我们先给出两个基本的写法，即代码1和代码2。
代码1：
#include <stdio.h>
int main () {
int M,N,p,q,r;
scanf("%d %d", &M, &N);
p = M>N? M:N; // p是较大的
q = M>N? N:M; // q是较小的
r = p%q; // r是余数
// 以下代码就是小学奥数(或者初等数论)里讲的辗转相除法，也叫欧几里得算法（Euclidean Algorithm）
while (r > 0) {
p = q;
q = r;
r = p%q;
} // 最后一个非零的余数r,就是M,N的最大公约数
printf("%d %d", q, M*N/q); // 最小公倍数就是两数之积除以最大公约数
return 0;
}
代码2：
#include <stdio.h>
int main () {
int M,N,p,q,r;
scanf("%d%d",&M,&N);
p = M>N?M:N;
q = M>N?N:M;
while(p%q) {
r = p%q;
p = q;
q = r;
}
printf("%d %d", q, M*N/q);
}
注意到：表达式 r = p%q 的值就是p%q，我们还可以对代码2稍加简化。
代码3：
#include <stdio.h>
int main () {
int M,N,p,q,r;
scanf("%d%d",&M,&N);
p = M>N?M:N;
q = M>N?N:M;
while (r = p%q) {
p = q;
q = r;
}
printf("%d %d", q, M*N/q);
}
又注意到，如果一开始p是M,N中较小的，而q是M,N中较大的，那么经过一轮循环以后，p就会变成M,N中较大的，q就会变成M,N中较小的。所以我们可以不用管M,N的大小，直接进行辗转相除。于是下面的代码4也是正确的。
代码4：
#include <stdio.h>
int main () {
int M,N,p,q,r;
scanf("%d%d",&M,&N);
p = M;
q = N;
while = p%q) {
p = q;
q = r;
}
printf("%d %d", q, M*N/q);
}
最后，我们还可以把求最大公因子的算法写成一个函数，就像下面这样
代码5：
#include <stdio.h>
int GCD (int p, int q) {
int r;
while (r = p%q) {
p = q;
q = r;
}
return q;
}
int main () {
int M,N,G;
scanf("%d%d",&M,&N);
G = GCD(M,N);
printf("%d %d", G, M*N/G);
}
更多PTA题目的的参考代码，可以在wx小程序里搜“PTA刷题助手”，或扫下面的二维码
