공약수

백준 2981 풀이 (검문, 유클리드 호제법, 약수 구하기)

이 문제는 정말 나의 탁월한 운빨로 풀게된 문제이다. 문제를 읽게 되면 그렇게 어려워 보이지 않는다. 읽고나서 바로 생각나는 것은 2부터 나누기 시작해서 다 나누어 떨어지면 되는거 아닌가? 하는 생각이 든다. 나도 당연히 그렇게 풀어볼까 하다가 조금이라도 연산을 줄이고자 나머지를 기준으로 값을 나누어 보기 시작했다. 물론 잘못된 방법이었다. 바로 풀릴리가 없지ㅋㅋㅋㅋ 그래서 고민하다가 도달한 결론은 노가다로 푸는게 아니고 무언가 규칙이 있을것이란 생각이었다. 테스트 케이스로는 6,34,38을 준다. 그래서 이걸로 값을 바꿔보기도 하다가 1씩 증가시켜보았다. 7, 35, 39 신기한것은 이렇게 1이 증가하여 전부 홀수가 되었음에도 같은 나머지를 만들기 위해서 2, 4가 필요한 것이었다. 그래서 각 값들의 ..