[CodeForces] Kuroni and Impossible Calculation (C++)

문제 링크: https://codeforces.com/contest/1305/problem/C

Problem - C - Codeforces

1. 주의할 점

- N의 범위가 20만이므로 N^2으로는 TLE가 발생한다.

- M의 범위가 1000이하라는 사실에 유의한다

 

2. 구현

- 입력으로 받은 수 An % M의 값이 이미 존재하는 경우, 파이값은 무조건 0이다

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int test, num, mod, tt;
	cin >> num >> mod;
	vector<int> v;
	bool zero = false;
	int result = 1;
	bool check[1001] = { false, };
	for (int i = 0; i < num; i++) {
		cin >> tt;
		int val = tt % mod;
		if (!check[val]) {
			v.push_back(tt);
			check[val] = true;
		}
		else {
			zero = true;
		}
	}
	if (mod == 1 || zero) result = 0;
	else {
		for (int i = 0; i < v.size() - 1; i++) {
			for (int j = i + 1; j < v.size(); j++) {
				int val = abs(v[i] - v[j]);
				val %= mod;
				result *= val;
				result %= mod;
				if (result == 0) break;
			}
			if (result == 0) break;
		}
	}
	cout << result;
	return 0;
}