2017-11-16

作者: jackjianshu | 来源:发表于2017-11-16 15:46 被阅读0次

一个普通人的日记 2017-11-16
小驴拉磨之iOS进阶-多线程（6）—— GCD 并发队列
天上掉下个涌泉桔
Rustls之源码分析总结（一）
自创小说处女作【五个人-爱情】第一回下：女生宿舍走秀定情
js事件兼容写法
季总结：维铭父母正面管教1801-150号-铭仔-3/90—20
处女作《原谅我喜欢你好多年》封面语、情节大纲、人物设定、
自创小说处女作【五个人-爱情】第二回上：互相爱慕情书表白
SSM项目简单整合

6．欧几里得辗转相除法

大家熟悉一个整数a被另一个整数b去长除，如果在余数小于除数之前，这个步骤能一直进行下去，如，a＝648，b＝7。我们得到商q＝92，余数r＝4，则648＝92·7＋4。我们可以把这个过程叙述为一个定理：如果a是任意一整数，b是任意一大于0的整数，则我们总能找到一个整数q，使a＝b·q＋r，其中0＜＝r＜b是－个整数

下面我们用这－定理来求两个整数的最大公因子，记d＝(a、b)表示最大公因子，这就是辗转相除法：对于任意两整数a、b，若a＝bq＋r (b＝／0)，则(a、b)＝(b、r)。这是因为对任意同时整除a和b的数u，有a＝su，b＝tu，那么r＝a－bq＝su－tuq＝(s－tq)u也能被u整除，反过来，每个整除b和r的整数v，有b＝s’v，r＝t’v，它也整除a，这是因为a＝(s’q＋t’)v，因此a和b的公因子集和b与r的公因子集相同。这就证明了上面所述定理。

例．求1804和328的最大公因子

首先按照普通除法得1804＝5·328＋164；第二步继续第一步得328＝2·164＋0；

所以d＝(328、164)＝(164、0)＝164