最大公约数算法之横向评测

Jalen at 
最大公约数简称 Gcd 当然还有一个简称 hcf 嘿嘿嘿(可我不敢用 hcf QAQ)求法有好多种穷举法碾转相除法欧几里得算法扩展欧几里得算法 Stein 算法碾转相减法利用位运算(不知道叫什么,非常快就对了) 算法介绍 1. 穷举法没什么说的 代码实现 int Gcd1(int a, int b) {int Gcd = 1, minn = min(a, b);for (int i=2; i r = a - kb = xg - kyg = (x - ky)g 即,g 也是 r 的约数。这样,g 就是 (b, r) 即 (b, a mod b) 的公约数。必要性:设 g 是 (b, a mod ……