문제
N개의 양의 정수가 주어졌을 때, 이 수들을 어떤 수 M으로 나눈 나머지가 모두 같게 되는 M(2 이상)을 모두 구하라.
입력
첫째 줄에 N (2 이상 100 이하), 둘째 줄부터 N개의 수가 주어진다 (1 이상 1,000,000,000 이하).
출력
가능한 M을 오름차순으로 공백으로 구분하여 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 6 34 38 | 2 4 |
풀이
인접 차이들의 GCD의 약수가 가능한 M이다.
- 수들을 오름차순 정렬한다
- 인접한 두 수의 차이를 구하고, 모든 차이의 GCD를 계산한다
- GCD의 2 이상인 약수를 모두 오름차순으로 출력한다
핵심 아이디어: 모든 수를 M으로 나눈 나머지가 같으면, 두 수의 차이는 M의 배수이다. 따라서 모든 차이의 GCD의 약수가 가능한 M이다.
코드
package day349;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Day338BOJ2981검문 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(arr);
int gcdVal = arr[1] - arr[0];
for (int i = 2; i < N; i++) {
gcdVal = gcd(gcdVal, arr[i] - arr[i - 1]);
}
for (int i = 2; i <= gcdVal; i++) {
if (gcdVal % i == 0) {
System.out.print(i + " ");
}
}
}
static int gcd(int a, int b) {
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return a;
}
}복잡도
- 시간: O(N log N + sqrt(G)) - 정렬 + GCD 약수 탐색 (G는 GCD 값)
- 공간: O(N)