반응형
문제
문제 설명
N개의 수를 M으로 나누었을 때, 나머지가 전부 같은 M을 찾는 문제
도저히 모르겠다. 아무래도 js로 다시 풀어야겠다.
성공 코드(참고: https://pangsblog.tistory.com/62)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader((System.in)));
int n = Integer.parseInt(br.readLine());
int numbers[] = new int[n];
for (int i = 0; i < n; i++) {
numbers[i] = Integer.parseInt(br.readLine());
}
br.close();
Arrays.sort(numbers);
int gcdNum = numbers[1] - numbers[0];
for(int i=2; i < n; i++) {
int dist1 = numbers[i] - numbers[i-1];
gcdNum = gcd(gcdNum, dist1);
}
searchM(gcdNum);
}
public static int gcd(int first, int second) {
if (second <= 0) return first;
int temp = first;
first = second;
second = temp % second;
return gcd(first, second);
}
public static void searchM(int number) {
List<Integer> list = new ArrayList<>();
list.add(number);
for (int i = 2; i <= Math.sqrt(number); i++) {
if (number % i == 0) {
if (i == number / i) {
list.add(i);
}
else {
list.add(i);
list.add(number / i);
}
}
}
Collections.sort(list);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < list.size(); i++) {
sb.append(list.get(i) + " ");
}
System.out.println(sb.toString());
}
}
반응형