发布于 ,更新于 

最大公约数

最大公约数

辗转相除法

例:

1
2
3
70 % 50 = 20
50 % 20 = 10
20 % 10 = 0

取模到0为止,此时10就是70、50最大公约数

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
using namespace std;
int main() {
int a,b,r;
cin >> a >> b;
while (a % b != 0){
r = a % b;
a = b;
b = r;
}
cout << b << endl;
return 0;
}

更相减损术

1
2
3
4
5
6
7
8
9
54 24
| 除以2(可除可不除,除后方便计算)
V
27 12
27-12=15 大减小
...
...

6-3=3

此处3=3,所以最大公约数为3