求最大公约数
1. 辗转相除法
-
原理：
- 代码：
#include <iostream>
using namespace std;
int gcd1(int x, int y)
{
return (x%y == 0) ? y : gcd1(y, x%y);
}
int gcd2(int x, int y)
{
int ans = 1;
while(x % y != 0)
{
ans = x % y;
x = y;
y = ans;
}
return ans;
}
int gcd3(int x, int y)
{
if(y != 0)
return gcd3(y, x%y);
return x;
}
2. 辗转相减法
-
原理：
- 代码：
#include <iostream>
using namespace std;
int gcd4(int x, int y)
{
while(x != y)
{
if(x > y)
x = x - y;
else
y = y - x;
}
return x;
}
3. 穷举法
- 代码：
int gcd5(int x, int y)
{
int tmp = 0;
for(tmp = x; ; tmp--)
{
if(x % tmp == 0 && y % tmp == 0)
break;
}
return tmp;
}
