求最大公约数有三种方法一种是辗转相除法，另一种是相减法，还有穷举法。
最大公倍数等于两数乘积/最大公约数。
- 辗转相除法
有两种实现方法一种是递归法另一种是不使用递归
递归：
1
2
3
4
5
6
| int fun(int a,int b)
{
if(a<b)
std::swap(a,b);
return b==0?a:fun(b,a%b);
}
|
非递归：
1
2
3
4
5
6
7
8
9
10
11
12
| int fun(int a,int b)
{
int temp;
if(b>a) std::swap(a,b);
while(b)
{
temp=a%b;
a=b;
b=temp;
}
return a;
}
|
- 相减法
1
2
3
4
5
6
7
8
9
| int fun(int a,int b)
{
while(a!=b)
{
if(a>b) a=a-b;
else b=b-a;
}
return a;
}
|
- 穷举法
首先保持第一个数为最大的值否则交换两个值，令i=m，开始递减，直到m和n同时除以i为0，此时输出最大公因数为max=i。
1
2
3
4
5
6
7
8
9
10
11
| int fun(int a,int b)
{
if(a<b) std::swap(a,b);
for(int i=a;i>1;i--)
{
if(a%i==0&&b&i==0)
return a;
}
}
|
负数的二进制：将这个负数的相反数的二进制求出来并对
每一位取反（这个过程叫取原码的反码），取反之后进行补码就行。