int gcd(int a,int b)//求俩个数最大公约数 { return b==0 ? a : gcd ( b , a % b); }
辗转相除法的证明
设俩数为 a , b (a,b),求它们最大公约数的步骤如下
设 q = a / b
r = a % b
a = bq + r (r小于b大于等于0）
如果 r = 0 则 b 是 a 与 b 的最大公约数
r = a - bq
设存在a 与 b 的最大公约数 d 且 a = sd b = gd
r = (s - gq) d // s - gq为常数,所以可得结论 a 与 b 的最大公约数一定也是 r 的最大公约数
原文：https://www.cnblogs.com/newstartCY/p/11438689.html