夢に僕らで帆を張って
来るべき日のために夜を超え

标签 欧几里得算法 下的文章

September 26, 2019

欧几里得算法&扩展欧几里得算法

欧几里得算法一、欧几里得(Euclid)算法又称辗转相除法,用于求两数最大公约数。$$(a,b)=(b,a\%b)$$代码:int gcd(int a,int b){ return b?gcd(b,a%b):a; }二、扩展欧几里得(Euclid)算法用于求解方程 $$ax+by=(a,b)$$ 的所有整数解 $(x,y)$ 。考虑 $$(a,b)=(b,a\%b)$$$\becau...