数学算法学习笔记集合

辗转相除法（欧几里得算法）：求最大公约数 (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 有...

Submit