백준 2981번 검문

문제 링크입니다: https://www.acmicpc.net/problem/2981

2981번: 검문

수학적 사고를 요구하는 문제였습니다.

어떠한 숫자를 m으로 나누었을 때 나머지가 r이라면 해당 숫자는 아래와 같이 표기할 수 있습니다.

v[i] = m * temp[i] + r

 

따라서, 나머지 r을 지워주기 위해서는 같은 나머지를 같는 숫자를 빼주면 되는데 이는 아래와 같이 표기할 수 있습니다.

v[i] - v[i - 1] = m * (temp[i] - temp[i-1]) + (r - r)

 

따라서, N개의 숫자를 입력받고 오름차순으로 정렬해준 뒤 (v[i] - v[i-1])의 최대공약수를 구한 뒤, 최대공약수의 약수를 오름차순으로 나열하면 되는 문제였습니다.

 

* 유클리드 호제법을 사용하는 문제가 간혹 있으므로 최대공약수를 구하는 함수는 외워두는 편이 좋습니다.

 

 

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~