[백준 17433] 신비로운 수 [Java]

문제

http://boj.ma/17433

17433번: 신비로운 수

 

---

풀이

문제 요약

N개의 정수를 M으로 나눈 나머지가 동일한 최대 M을 구하자.

아이디어

어떤 수 $a_{1}$, $a_{2}$를 M으로 나눈 나머지가 r로 같아야 한다. 이때 두 수의 차는 $(q_{2} - q_{1})*M$으로 M의 배수가 된다.

N개의 수의 차들에 대해 가장 큰 GCD는, N개의 수의 차들에 대한 가장 큰 공통 약수가 된다.

이는 N개의 모든 수를 나누었을 때 나머지가 전부 같아지는 최대 M이 된다.

			Arrays.sort(A);
			int[] diff = new int[N - 1];
			for (int i = 0; i < N - 1; ++i) {
				diff[i] = A[i + 1] - A[i];
			}
			int commonGCD = diff[0];
			for (int i = 1; i < N - 1; ++i) {
				commonGCD = gcd(commonGCD, diff[i]);
			}
			if (commonGCD == 0) {
				sb.append("INFINITY\\n");
			} else {
				sb.append(commonGCD).append("\\n");
			}

풀이 시간

20분

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/normal/17433.java

problem-solving/baekjoon-online-judge/normal/17433.java at main · rogi-rogi/problem-solving