0
已解决
高级天翼
如题，谁能给我个最快的、时间复杂度最低的算法？我目前只会用递归法。
李泽远在2020-05-10 21:22:46追加了内容
这里数据能达到1*10^9，循环肯定会超。
0
已采纳
初级天翼
用（a,b）表示a和b的最大公约数
有定理： 已知a,b,c为正整数，若a除以b余c，则（a,b）=(b,c)。 （证明过程请参考其它资料）
例如：求gcd（319，377）：
∵ 377÷319=1（余58）
∴gcd（377，319）=gcd（319，58）；
∵ 319÷58=5（余29），
∴ gcd（319，58）=gcd（58，29）；
∵ 58÷29=2（余0），
∴ gcd（58，29）= 29；
∴ gcd（319，377）=29.
0
新手天翼
/* 迭代法（递推法）：欧几里得算法，计算最大公约数 */
int gcd(int m, int n)
{
while(m>0)
{
int c = n % m;
n = m;
m = c;
}
return n;
}
int cd(int x, int y)
{
int i, j, t;
if (x == 0)
return y;
if (y == 0)
return x;
for (i = 0; 0 == (x & 1);x >>= 1, ++i);
for (j = 0; 0 == (y & 1);y >>= 1, ++j);
if (j < i)
i = j;
for (;;)
{
if (x < y)
t = y, y = x, x = t;
if (0 == (x -= y))
return y << i;
for (;0 == (x & 1);x >>= 1);
}
}上述两种算法都是求最大公约数，但是谁更快呢？前者是经常使用的，而且代码简单
但是后者是二进制的按位操作，似乎更快，实际结果也是后者更快
在一些题目中掌握后者基本上就与超时无缘了，但是，这代码。。。。真的很难懂。
唉，菜鸡（我）。
还有一种二进制加速gcd，了解一下
int gcd(int a,int b)
{
while(b^=a^=b^=a%=b);
return a;
}
0
初级天翼
辗转相除法可以的叭
0
高级光能
如果你要求a和b的公因数，辣么辗转相除法/递归
如果是最大公因数的话，__gcd(a,b)//别忘了头文件
0
被禁言
初级光能
辗转相除法or递归
PS：你问这个干什么
0
中级天翼
辗转相除法
