viod

题解

/ 注册

全部文章 / 题解（共1篇）

题解 | #求最小公倍数#

求最大公约数常用的有两种方法，一是九章算术中的更相减损术：大数减小数直到相等，相等的数即最大公约数，该算法时间复杂度约为O(N)；二是欧几里得的辗转相除法：大数除以小数取余数(相当于模运算)，直到余数为零时(也即模运算为零时)的除数(也即模数)就是最大公约数，该算法时间复杂度约为O(logN)。...

最大公约数最小公倍数更相减损术辗转相除法欧几里得

2022-04-02

0 421