유클리드 호제법

 0. MOD 연산이란? 

두 값을 나눈 나머지를 구하는 연산이다!!
ex) 10 MOD 4 = 2 // 10 % 4 = 2

 

 1. 유클리드 호제법 요약 

1️⃣ a % b 수행, 결과값 c(나머지)
2️⃣ b % c 수행
3️⃣ 2️⃣ 반복, 나머지가 0이 되면 그 연산의 나누는 수(작은 수)를 최대공약수로 선택

 

분명 이산에서 배운건데 까먹었다.. 기억해두자

백준 1934 1850 1033

 

 

 2. 확장 유클리드 호제법