数学算法学习笔记集合
发表于 2022-07-05 |更新于 2022-07-10 |学习笔记
辗转相除法(欧几里得算法):
求最大公约数 (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 - bq a÷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