백준 - 2981 검문 풀이

문제

2981 검문

풀이

1. M 구하기

식 정리

A_n: 입력 받은 수
a_n: 몫
M: 제수
r: 나머지

A_n / M = a_n … r

---

A_n = a_n * M + r

---

A₀ = a₀ * M + r
A₁ = a₁ * M + r
…
A_n-1 = a_n-1 * M + r
A_n = a_n * M + r

---

r = A_n-1 - a_n-1 * M
r = A_n - a_n * M

---

A_n - a_n * M = A_n-1 - a_n-1 * M
A_n - A_n-1 = a_n * M - a_n-1 * M

---

A_n - A_n-1 = M * (a_n - a_n-1)

결론,
M은 (A_n - A_n-1)의 약수이다.
모든 M을 구하기 위해서는 (A_n - A_n-1)들의 모든 약수를 구하면 된다.
(A_n - A_n-1)들의 모든 약수는 (A_n - A_n-1)들의 최대 공약수의 모든 약수이다.

(A_n - A_n-1)들의 최대 공약수를 구하자!

코드

var gcdValue = 0
(1..inputs.lastIndex).forEach { gcdValue = gcd(kotlin.math.abs(inputs[it] - inputs[it - 1]), gcdValue) }

2. 최대 공약수 구하기

유클리드 호제법

유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r’를 구하고, 다시 r을 r’로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

유클리드 호제법

코드

fun gcd(a:Int, b:Int):Int = when(b) {
    0 -> a
    else -> gcd(b, a%b)
}

3. 최대 공약수의 모든 약수 구하기

모든 약수 구하기

n보다 작은 n을 나누면 나머지가 0이 되는 수가 있는 지 확인하면 된다. 1은 제외한다는 조건이 있기때문에 2부터 n까지 모든 수를 검사하면 된다.
하지만, 시간이 이 많이 걸린다.(해보니 시간 초과에 걸리진 않지만, 시간 차이는 많이 난다.)
최적화를 하면, 2부터 n까지가 아닌 ⌊√n⌋까지만 진행하면 된다.
수가 수를 나누기 위해서는 그 몫이 항상 필요하며 나누는 수와 몫 중 어느 하나는 반드시 √n이하이기 때문이다.[소수 (수론)]

코드 1: 2부터 n까지 검사

val output = StringBuilder()
(2..gcdValue).forEach { if(gcdValue % it == 0) output.append(it).append(' ') }

코드 2: 2부터 ⌊√n⌋까지 검사(최적화)

val outputSet = mutableSetOf(gcdValue)
val sqrtGcdValue = kotlin.math.sqrt(gcdValue.toDouble()).toInt()
(2..sqrtGcdValue).forEach { if(gcdValue % it == 0) {outputSet.add(it); outputSet.add(gcdValue/it); }}

val output = StringBuilder()
outputSet.sorted().forEach{ output.append(it).append(' ') }

답

kotlin code

fun main() {
    val inputs = IntArray(readln().toInt()) { readln().toInt() }

    var gcdValue = 0
    (1..inputs.lastIndex).forEach { gcdValue = gcd(kotlin.math.abs(inputs[it] - inputs[it - 1]), gcdValue) }
    
    val outputSet = mutableSetOf(gcdValue)
    val sqrtGcdValue = kotlin.math.sqrt(gcdValue.toDouble()).toInt()
    (2..sqrtGcdValue).forEach { if(gcdValue % it == 0) {outputSet.add(it); outputSet.add(gcdValue/it); }}

    val output = StringBuilder()
    outputSet.sorted().forEach{ output.append(it).append(' ') }

    println(output)
}

fun gcd(a:Int, b:Int):Int = when(b) {
    0 -> a
    else -> gcd(b, a%b)
}

Reference

• 유클리드 호제법
• 소수 (수론)