문제 설명트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다.상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다.먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다.N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오.https://www.acmicpc.net/problem/2981 제한 사항 풀이문제를 요약하면, N개의 수가 주어지고 이를 M으로 나눌 때 나머지가 모두 같아지는 M을 전부 구하는 것이다. 문제는 간단하지만 수학적인..
최대공약수와 최소공배수를 구하는 문제이다. 선형적인 탐색법으로 작은 수전까지 하나씩 나누어 보고 둘 다 나누어 떨어지는 수 중 가장 큰 수를 구하면 되겠지만, 다른 수학적인 방법을 이용하여 최대공약수를 구한 뒤 그를 이용하여 최소 공배수까지 구하는 방법이 있다. 임의의 수 a, b가 있다 가정하자. (단, a > b) a를 b로 나누면 몫과 나머지가 있을 것이다. 그러면 그 나머지로 나누는 수 (b)를 또 나눈다. 이를 반복하다 나누는 수 (b)가 0이 되면 나누어지는 수 a를 return 한다. 그림을 보면 x가 최대공약수라 할 때, a = 8x b = 3x a% b = 2x이다. 우리는 x를 구해야 하기 때문에, 나머지가 0이 될 때, 즉 모든 수가 나누어 떨어질 때까지 계속해서 b를 나머지로 나눈다..
