CSP-J最大公约数与最小公倍数

最大公约数和最小公倍数

最大公约数gcd和最小公倍数lcm是普及组常考的算法之一，也是数论中一个重要的分支。想学好数论，最大公约数和最小公倍数是你必须要掌握的。

例题选讲

就以P1029为例，就是给出两个数的最大公约数和最小公倍数让你求出这两个数一共有多少种。

那么我们看到这道题以后，要养成一个分析样例的习惯。我们来分析一下样例，两个数的最大公约数为3，最小公倍数为60，而我们知道两个数的乘积=最大公约数乘最小公倍数，所以这两个数的乘积为180。而这两个数肯定在最大公约数和最小公倍数之间，所以我们可以从最大公约数3开始枚举，一直枚举到最小公倍数60，只要满足，个数+1，最后输出个数，本题就OK了。

本题单精选出 10 道比较经典的普及组难度的题目，目的是让大家熟悉数论并比较好的掌握最大公约数和最小公倍数的实际应用。