2981번: 검문 - Kotlin (유클리드 호제)

2981번: 검문

문제

트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다.

상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다.

먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다.

N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오.

입력

첫째 줄에 종이에 적은 수의 개수 N이 주어진다. (2 ≤ N ≤ 100)

다음 줄부터 N개 줄에는 종이에 적은 수가 하나씩 주어진다. 이 수는 모두 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. 같은 수가 두 번 이상 주어지지 않는다.

항상 M이 하나 이상 존재하는 경우만 입력으로 주어진다.

출력

첫째 줄에 가능한 M을 공백으로 구분하여 모두 출력한다. 이때, M은 증가하는 순서이어야 한다.

 

 

나의 풀이

이 문제는 수학적으로 접근해야 해결할 수 있다.

 

두 숫자를 공통된 숫자로 나눴을 때 같은 나머지를 가질려면 어떤 조건을 가질지 알아보아야 한다. 문제에서 주어진 6과 34로 접근해보도록 하겠다.

 

6과 34를 어떤 숫자 num으로 나눴을 때의 나머지는 다음과 같이 표시할 수 있다.

 

6 = 몫 1 * num + 나머지

34 = 몫 2 * num + 나머지

 

아래의 식에 위의 식을 뺀다면 아래와 같은 식을 얻을 수 있다.

 

34 - 6 = (몫 2 - 몫 1) * num

 

위의 식은 이렇게 표시할 수도 있다.

 

28 / num = 몫 3

  

이 말은 28을 num으로 나눴을 때, 나머지가 없다는 말이다. 그럼 num이 될 수 있는 값은 28의 약수가 된다.

 

그럼 이제 num이 될 수 있는 값들을 찾을 수 있다. 다만 매번 그렇게 약수를 찾는 것은 번거롭다. 기본적으로 두 숫자의 약수는 최대 공약수의 약수와 같다. 이를 이용하면 최대 공약수를 구할 수 있다.

 

다음은 최대 공약수의 약수를 출력하면 된다.

 

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()

    val number = mutableListOf<Int>()

    repeat(n) {
        number.add(readLine().toInt())
    }

    number.sort()

    var temp = number[1] - number[0]

    for (i in 1 until n - 1) {
        temp = gcd(temp, number[i + 1] - number[i])
    }

    val ans = mutableListOf<Int>()

    for (i in 2..temp) {
        if (temp % i == 0)
            ans.add(i)
    }

    ans.forEach {
        print("$it ")
    }
}

fun gcd(p: Int, q: Int): Int {
    if(q == 0) return p
    return gcd(q, p % q)
}