[BOJ/Gold 5] 백준 17433 신비로운 수(C++)

문제 링크

https://www.acmicpc.net/problem/17433

17433번: 신비로운 수

 

문제

0이 아닌 정수 N개가 주어졌을 때, 0이 아닌 정수 M이 다음 성질을 만족하면 M은 N개의 정수에 대해 신비로운 수라고 한다.

• N개의 정수를 M으로 나눈 나머지가 모두 같다.

임의의 N개의 정수에 대해 신비로운 수는 적어도 하나 이상 존재한다. 예를 들어, 1은 N개의 정수와 상관없이 항상 신비로운 수이다.

N개의 수가 주어졌을 때, N개의 정수에 대해 신비로운 수 중에서 가장 큰 수를 구해보자.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 두 줄로 이루어져 있고, 첫째 줄에 N, 둘째 줄에 N개의 정수가 주어진다.

출력

각각의 테스트 케이스마다 N개의 정수에 대한 가장 큰 신비로운 수를 출력한다. 만약 신비로운 수가 무한대로 발산하는 경우 "INFINITY"를 출력한다.

제한

• 1 ≤ N ≤ 2,000
• -109 ≤ N개의 정수 ≤ 109

예제 입력 1

4
5
2 4 6 8 10
5
162 72 54 63 57
5
-20 -30 -50 80 75
4
5 5 5 5

예제 출력 1

2
3
5
INFINITY

노트

임의의 정수 p를 0이 아닌 임의의 정수 q로 나눈 나머지는 0 ≤ p - a×q < q를 만족하는 유일한 정수 a에 따라서 정해진다. 이때 나머지는 p - a×q이다.

예를 들어, p = 7, q = 3인 경우 나머지는 1, p = -7, q = 3인 경우 나머지는 2이다.

알고리즘 분류

• 수학

풀이

이 문제랑 거의 동일하다.

2981번: 검문

다만 M이 될 수 있는 수를 모두 구하는 게 아니고, M이 될 수 있는 수 중 최댓값을 구하는 것이다.

M이 존재하지 않는다면 INFINITY를 출력한다. 본인은 M을 일단 0으로 초기화시키고, 0에서 다른 값으로 초기화되지 않는다면 신비로운 수 M이 무한대로 발산한다고 보았다.

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);

using namespace std;
int T, N;
vector<int> Vec;
vector<int> Sub;
int Answer;

void Init() {
	Vec.clear();
	Sub.clear();
	Answer = 0;
}

int GCD(int N, int M) {
	while (1) {
		int R = N % M;
		if (R == 0) {
			return M;
		}
		N = M;
		M = R;
	};
}

void Settings() {
	sort(Vec.begin(), Vec.end());
	if (Vec.size() > 1) {
		for (int i = 0; i < ((int)Vec.size() - 1); i++) {
			if (Vec[i + 1] - Vec[i] > 0) {
				Sub.push_back(Vec[i + 1] - Vec[i]);
			}
		}
	}
	sort(Sub.begin(), Sub.end());
	Sub.erase(unique(Sub.begin(), Sub.end()), Sub.end());
	if (Sub.size() == 1) {
		Answer = Sub[0];
	}
	else if (Sub.size() > 1) {
		Answer = GCD(Sub[1], Sub[0]);
		for (int i = 2; i < Sub.size(); i++) {
			Answer = GCD(Sub[i], Answer);
		}
	}
}

void Find_Answer() {
	if (Answer == 0) {
		cout << "INFINITY\n";
	}
	else {
		cout << Answer << "\n";
	}
}

void Input() {
	cin >> T;
	while (T--) {
		Init();
		cin >> N;
		for (int i = 0; i < N; i++) {
			int I;
			cin >> I;
			Vec.push_back(I);
		}
		Settings();
		Find_Answer();
	};
}

int main() {
	FASTIO
	Input();

	return 0;
}