👩💻 Join our community of thousands of amazing developers!
辗转相除法(欧几里得算法):求最大公约数 (a,b),a>b(a, b), a > b(a,b),a>b。有:a÷b=q…ra=bq+rr=a−bqa \div b = q \ldots r\\a = bq + r \\r = a - bqa÷b=q…ra=bq+rr=a−bq辗转相除法指出: gcd(a,b)=gcd(b,r)\gcd(a, b) = \gcd(b, r)gcd(a,b)=gcd(b,r)我们设ddd 为 aaa 和 bbb 的任意一个公约数。以及m=a÷d, n=b÷dm = a \div d,\ n = b \div dm=a÷d, n=b÷d那么:a=dm, b=dnr=a−bq=dm−(dn)q=d(m−nq)a = dm,\ b = dn\\\begin{align*}r &= a - bq\\&= dm - (dn)q\\&= d(m - nq)\end{align*}a=dm, b=dnr=a−bq=dm−(dn)q=d(m−nq)因为 r=d(m−nq)r = d(m - nq)r=d(m−nq)。所以我们可以得出,如果 aaa 和 bbb 有...