유클리드 호제법

유클리드 호제법 이란 두 수의 최대 공약수(GCD, Great Common Divisor) 를 구하는 매우 효율적인 시간복잡도의 알고리즘이다.

유클리드 호제법을 활용해 여러가지 수를 구할 수 있다.

gcd를 구했다면 두 수는 각각 gcd*A, gcd*B 의 형태일 것이고 이때 A와 B는 서로소이다.

회귀법을 통한 증명으로 A, B가 서로소가 아니라고 가정한다면 두 수는 1이 아닌 임의의 양의 정수 m을 공통인수로 갖는다.

즉, A = a*m, B = b*m 형태가 되지만 이렇게 된다면 gcd가 최대 공약수라는 전제가 모순이 된다. gcd*m이 최대 공약수가 될 수 있기 때문이다.

따라서 gcd를 구하고 두 수에 gcd를 나누면 서로소가 남게된다. (서로소의 최대 공약수는 1이다)

또 최소 공배수(LCM, Least Common Multiple) 는 두 수를 곱한 뒤 최대 공약수 gcd를 나누면 된다. 즉, LCM=A*B/gcd 이다.

문제

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

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

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

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

입력

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

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

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

출력

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

// 2022-02-18
// https://www.acmicpc.net/problem/2981

import java.io.*
import java.util.*
import kotlin.math.sqrt

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    val arr = mutableListOf<Int>()
    val answer = sortedSetOf<Int>()
    repeat(n){arr.add(readLine().toInt())}
    arr.sortBy { -it }
    var sub = arr[0]-arr[1]
    var gcd = 0
    for(i in 0 until arr.lastIndex) gcd = gcd(maxOf(gcd,arr[i]-arr[i+1]), minOf(gcd,arr[i]-arr[i+1]))
    answer.add(gcd)
    for(i in 2..sqrt(gcd.toFloat()).toInt()){
        if(gcd%i==0){
            answer.add(i)
            answer.add(gcd/i)
        }
    }
    answer.forEach{print("$it ")}
}

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