天才一秒记住【一路小说网】地址：https://www.waynot.net
他在黑板上写下算法步骤：
1.用较大数除以较小数，得到余数。
2.用之前的除数除以这个余数，得到新的余数。
3.重复这个过程，首到余数为零。
4.此时，最后的除数就是最大公约数。
他以1071和462为例进行演示：
1071÷462=2…147
462÷147=3…21
147÷21=7…0
所以，GCD（1071，462）=21。
“哇！
这么快？”
林薇薇看着简洁的步骤，对比自己草稿纸上的分解过程，惊讶地睁大了眼睛。
张涛也挠头：“这么简单？为啥这样算出来就是对的了？”
李浩眼中闪过领悟的光芒：
“我明白了！
这个算法的核心在于GCD（a，b）=GCD（b，amodb）这个性质！
它把大问题转化成了更小的问题，递归进行！”
“没错！”
苏白赞赏地看了李浩一眼：
“这就是算法的‘高效’所在——它通过不断缩小问题的规模，避免了复杂的质因数分解。
我们可以试着证明一下这个关键性质…”
接下来的时间，苏白引导大家一步步推导这个性质的证明。
虽然涉及一些整数的带余除法性质，但在苏白清晰的讲解和李浩的补充下，林薇薇和张涛也勉强跟上了思路，感受到了数学逻辑的严谨之美。
“太神奇了……”
林薇薇看着最终的证明过程，喃喃道：
“感觉像是打开了一扇新窗户。”
张涛虽然有些步骤没完全吃透，但也咂咂嘴：
“反正比分解质因数快多了！
这算法牛逼！”
李浩则己经开始思考：
“这个算法的时间复杂度是多少？大概和位数的对数成正比吧？比指数级分解快太多了。”
本章未完，请点击下一章继续阅读！若浏览器显示没有新章节了，请尝试点击右上角↗️或右下角↘️的菜单，退出阅读模式即可，谢谢！