[C++] 유클리드 호제법

문제풀이랑 개념을 같이 적어두니 헷갈려서 개념만 적어두는 게시글을 새로 만들었다

GCD(Greatest Common Divisor)
GCD란 최대공약수를 의미한다.

최대공약수를 구할 땐 유클리드 호제법을 이용하는게 편하다. 유클리드 호제법이란, a b의 최대공약수가 a%b(나머지) b의 최대공약수가 같다는 것을 이용하는 것이다.

---

예를 들어 15와 10이 있다고 해보자.
a=15, b=10이라고 하면 a%b=5, b=10이 된다.
이 a%b값을 a에 대입하자.

x%y를 할 때에는 x>y여야하므로
둘의 자리를 바꿔줘야한다

그러면 a=10, b=5가 된다.
나머지가 0이 될 때까지 해보자.

a%b=5, b=5가 된다.
a%b를 a에 대입하면
a=5, b=5가 되고
a%b = 0이 된다.

0이 되면 작은 값인 b를 리턴한다.
그러면 최대공약수가 b값, 즉 5가 된다

---

예를 들어 7과 3이 있다고 해보자
a=7, b=3이다.
a%b=1, b=3이다.

a%b를 a에 대입해주면 a=1, b=3이다.
a값이 더 커야하므로 둘의 자리를 바꿔주면 a=3, b=1이다.
a%b를 해주면 0이다. 3나누기 1은 몫이 3, 나머지가 0이다.
a%b=0이라면 이때 b 값이 GCD다. 즉 1이 최대공약수가 된다.

---

최대공약수를 G, 최소공배수 L이라 하자
G*L = A*B 이다. (수학적 공식이라고 한다.)
A = G*a, B=G*b이라고 하면 (이때 a, b는 서로소이다. 왜냐하면 최대공약수 G로 공통부분을 끄집어 냈으므로)
G*L = G*a*G*b가 되고 약분하면 L/G=a*b가 된다.






[C++] 백준 알고리즘 9613 GCD 합 (유클리드 호제법) (tistory.com)

[C++] 백준 알고리즘 9613 GCD 합 (유클리드 호제법)

[C++] 백준 알고리즘 2436 후보 추천하기 (유클리드 호제법) (tistory.com)

[C++] 백준 알고리즘 2436 후보 추천하기 (유클리드 호제법)