考虑到有少数同学做的是比较快的，在攻坚的路上容易遇上难题，本文优先选取一些难度较高的题目进行解析。由于1062和1063都是利用辗转相除法来解决的，故这里放在一起讨论。
1062:最大公约数
- 题目描述
输入两个不大于10的9次方的正整数，输出其最大公约数。 - 输入
输入两个正整数m和n，数据之间用空格隔开。 - 输出
输出一个整数，表示m和n的最大公约数。 - 提示
请查阅欧几里得定理及辗转相处法。 - 参考代码：
#include<stdio.h>
int main()
{
int m,n,r;
scanf("%d%d",&m,&n);
while(r=m%n,r!=0){
m=n;//将较小值保存给较大值
n=r;//将余数保存给较小值
}//利用辗转相除法处理m,n.得到最大公约数
printf("%d\n",n);
return 0;
}
- 代码解析:
我们可以看到，本题唯一比较陌生的点只有循环里的内容而已。循环里面是通过反复用m和n的余数去进行计算，即通过反复求余，得到其最后已经没有余数的结果。这里利用的是辗转相除法。接下来我们通过本题来解析一下辗转相除法的运用（欧几里得定理就是辗转相除法）
1.首先我们回到题目内容本身，题目要求求的是最大公约数，关于最大公约数的定义不懂的可以自己看一下。
2.要求最大公约数，最简单的方法就是辗转相除法，辗转相除法的用法是是：用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。
3.这里我们先定义一个额外的值，用来保存两个数的余数。这里运用while语句，把计算过程放在循环语句的钟变化的一项，并把余数=0作为其限制退出的条件，然后，在循环语句中，把较小值赋值给较大值，把余数赋值给较小值，并继续下一次的循环，直到，r=0，退出循环，这时上一次保存的n值就是初始两个正整数的最大公约数。
这里如果初始n与m的大小并无影响，倘若初始n>m时，m%m依然有其余数，例如本题中会出现，4%6=4的情况，然后通过下面的两次交换，会使二者正常进行循环，直到求出最大公约数。
1063：最大公约与最小公倍
- 题目描述
输入两个正整数，输出其最大公约数和最小公倍数。 - 输入
输入两个正整数n和m（n,m<=1000000)。输入保证最终结果在int范围内。 - 输出
输出两个整数，用空格隔开。表示m和n的最大公约数和最小公倍数。 - 提示
注意运算过程中的溢出问题 - 参考代码：
#include<stdio.h>
int main()
{
int a, b, r;
int copyA, copyB;
scanf("%d%d", &a, &b);
copyA = a;
copyB = b;
while(r = a % b, r != 0)
{
a = b;
b = r;
}
printf("%d %d\n", b, copyA / b * copyB);
return 0;
}
- 代码解析:
1063相比较于1062，仅仅只是多了一个求最小公倍数的输出而已。那么关于求取最小公倍数的方法其实非常多，而且大多不难，这里使用的写法只是我个人觉得比较简单的一种解法：两数相乘再除于最大公约数。
但在本题中，题目有明确提示注意过程中的溢出问题，int的定义是有上限的，如果数值过大时，则会导致数值溢出，答案错误，所以在本题中需要用 a/ 最大公约数* b。
求最小公倍数还有其他许多不同的方法，就不在此一一讲述了。
网友评论