为了让同学们能够利用零散时间学习NOIP，辽竞委经过课程调研后，尝试采用文字版公益课进行教学。课程共分十期，聘请NOI国赛选手按照竞赛大纲归纳知识点，采用文字和视频讲解，结合练习题和题解帮助同学们快速掌握NOIP的重点和难点。由于课程都是利用业余时间编写，无法保证定期推出课程，我们尽量每周三，周末推出两期内容供大家学习，不便之处请大家谅解。文字公益课处于探索阶段，希望大家多提意见和建议，对于课程中的问题可以在留言区提问，我们会尽快进行解答。

《跟我学NOIP》面向全社会征集文字课程内容。欢迎竞赛教师，竞赛学生和社会机构踊跃投稿，共同为信息学普及和发展贡献一份力量。

上期作业解析（感谢51nod提供的视频）

第四课 GCD和LCM

GCD的求法

1、枚举法

枚举出a，b两个数中最小数到1的所有数，判断能否整除a和b。 

2、    质因数分解法

根据唯一分解定理，将a和b分解成质因数的形式，然后分别取两个数相同质因数的最小幂次的乘积即为gcd（a,b）。

比如：a=36=2^2*3^2 ， b=48=2^4*3^1，根据上述定理可得出gcd（36，48）=2^min(2,4)*3^min(2,1)=2^2*3^1=12

代码参照上节课习题

3、    更相减损数（辗转相减法）

方法如下：gcd（a，b）=gcd（b,a-b）  (a>=b)

代码如下：

4、    欧几里得（辗转相除法）

方法如下：gcd（a，b）=gcd（b,a mod b）

代码如下：

5、       二进制

对于高精度计算还可以采用二进制算法，本课程不做重点讨论。

LCM的求法

方法如下：两个数a，b的最大公倍数lcm(a,b)=a*b/gcd(a,b)，因此只需要将gcd的代码稍作修改即可得到lcm的代码。

巩固练习：

给出N个正整数，找出N个数两两之间最大公约数的最大值。例如：N = 4，4个数为：9 15 25 16，两两之间最大公约数的最大值是15同25的最大公约数5。

作业提交评测请登录：

http://class.51nod.com/Course/Problem.html#!#courseProblemId=390&classId=22

作业解析：

将在下次”跟我学NOIP”给出题解，敬请关注！

往期链接：

辽宁省信息学文字公益课《跟我学NOIP》开课啦！第一课:快速幂

辽宁省信息学文字公益课  《跟我学NOIP》开课啦！第二课:质数和约数

辽宁省信息学文字公益课《跟我学NOIP》开课啦！第三课:常见质数筛法

公益课发起人

--end--

声明：本文章由网友投稿作为教育分享用途，如有侵权原作者可通过邮件及时和我们联系删除：freemanzk@qq.com