转自Armin’s blog 数论是个好东西。 欧几里德算法(gcd) 欧几里德算法又称辗转相除法,用于计算两个正整数a,b的最大公约数。 定理 g c d ( a , b ) = g c d ( b , a gcd(a,b)=gcd(b,a gcd(a,b)=gcd(b,a m o d mod mod b ) b) b) 特别的: g c d ( a , 0 ) = a gcd(a,0)=a g...