유한소수 판별하기
https://school.programmers.co.kr/learn/courses/30/lessons/120878
그 놈의 최대공약수가 문제다.
전에도 최대공약수가 어려웠다.
gcd를 쓰기 싫다.
유클리드 호제법은 다음과 같다.
a,b가 최대 공약수 c를 가지면, a>=b일 때 a를 b로 나눈 나머지 r이...
??
a = bq + r
r = bq - a
a,b의 최대 공약수가 g라고 하자.
r또한 g로 나눌 수 있다.
b와 r은 g를 공약수로 한다.
이 때, g가 최대공약수가 아니라고 가정하면
b=gg'b', r=gg'r'이 된다.
이는 a = bq + r에서
a = gg'b' + gg'r'이 되어??????
-> a와 b의 최대공약수가 gg'가 되어버리므로 g는 최대공약수가 된다.
정리할 필요가..
