오구의코딩모험

문제 3줄 요약 1. 상근이는 심심하다. 2. N개의 숫자가 종이에 있다. 3. 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게하는 M을 모두 찾아라 정수론 관련 문제는 딱 봐도 직관적으로 느껴지는게 없어서 힘든 것 같다.. (나는 그렇다. 다른 사람들은 직관적으로 보인다고 하더라) 저번 문제의 에라토스테네스의 체 같은 경우는 나름 이해하기 쉬웠지만, 이번엔 최대공약수를 구하는 "유클리드 호제법" 과 관련된 문제였다. 물론 위의 호제법을 몰랐기에 1부터 수를 늘려가며 비교해볼까 했지만, 당연하게도 수가 10억보다 같거나 작은 자연수기에 빠르게 포기하고 유클리드 호제법을 구글링하였다. https://namu.wiki/w/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C%20%ED..