만득

코딩 공부 정리용

​

© 2021. All rights reserved.

백준 2981 검문

23 Jun 2021

https://www.acmicpc.net/problem/2981

n개의 숫자를 m으로 나누었을 때 나머지가 모두 같게 되는 m을 모두 찾는 문제이다. n개의 숫자를 m으로 나누었을 때 나머지가 모두 같으려면 다음의 형태로 숫자들이 나타날 것이다.

xi = mq(xi) + r

이 때 임의의 두 숫자를 빼면 나머지가 같기 때문에 m|(xi - xj)인 m이 존재하게 된다. 따라서 이를 활용하여 숫자들을 오름차순 정렬을 시킨 후 이웃한 숫자끼리의 차들에 대해서 gcd를 계산해주면 m을 찾을 수 있다.

num.sort()
var bm = num[1]-num[0]
for i in 2..<n {
    bm = gcd(a: bm, b: num[i]-num[i-1])
}

만약 m이 여러개가 존재한다하면 gcd는 최대 공약수를 찾아주는 것이기 때문에 m값들의 최소 공배수를 얻게 된다. 따라서 최종적으로 얻어낸 bm값에 대해서 1과 본인을 제외한 모든 인수를 구해주면 원하는 결과를 얻을 수 있다.

let n = Int(readLine()!)!
var num:[Int] = []
for _ in 1...n {
    num.append(Int(readLine()!)!)
}
num.sort()

var bm = num[1]-num[0]
for i in 2..<n {
    bm = gcd(a: bm, b: num[i]-num[i-1])
}

var index = 2
var result:[Int] = [bm]
while index*index <= bm {
    if bm%index == 0 {
        result.append(index)
        if index*index != bm {
            result.append(bm/index)
        }
    }
    index += 1
}
result.sort()
var str = ""
for i in result {
    str += "\(i) "
}
print(str)

func gcd(a: Int, b: Int) -> Int {
    if a%b == 0 {return b}
    else {return gcd(a: b, b: a%b)}
}

Related posts