GitPinkRabbit/Number-Theory-in-Competitive-Programming

Part 1 中 Euclid 算法(辗转相除法)的正确性证明需要修改

GitPinkRabbit opened this issue · 0 comments

显然,直接给出 gcd(a, b) = gcd(b, a % b) 这一结论仅有利于 Euclid 算法本身的分析,但失去了很多拓展性。应该先解释为 gcd(a, b) = gcd(a - b, b) 即更相减损术。由此即可解释〔区间加,区间 gcd〕的差分做法([NOI 2012] 魔幻棋盘),还可以后续通过 Bézout 定理使用整系数线性组合的角度来解释。