# D. Yet Another Array Problem [문제 링크](https://codeforces.com/contest/2167/problem/D) ## Problem Statement You are given an integer $n$ and an array $a$ of length $n$. Find the smallest integer $x$ ($2 \le x \le 10^{18}$) such that there exists an index $i$ ($1 \le i \le n$) with $\gcd^{\ast}(a_i, x) = 1$. If no such $x$ exists within the range $[2,10^{18}]$, output $-1$. ## Input The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Each of the following $t$ test cases consists of two lines: The first line contains a single integer $n$ ($1 \le n \le 10^{5}$) — the length of the array. The second line contains $n$ space-separated integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^{18}$). It is guaranteed that the total sum of $n$ across all test cases does not exceed $10^{5}$. ## Output For each test case, output a single integer: the smallest $x$ ($2 \le x \le 10^{18}$) such that there exists an index $i$ with $\gcd(a_i, x) = 1$. If there is no such $x$ in the range $[2,10^{18}]$, print $-1$. ## Footnote $\gcd(x,y)$ denotes the greatest common divisor (GCD) of integers $x$ and $y$. ## 풀이 최대한 많은 소수들의 곱으로 이루어진 수라 하더라도, 포함된 소수의 종류가 많지 않기에 브루트포스로 풀립니다. ``` c++ #include<bits/stdc++.h> using namespace std; typedef long long ll; ll a[100000]; int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) { int n; cin >> n; for(int i=0;i<n;i++) cin >> a[i]; for(int i=2;;i++) { bool chk=false; for(int j=0;j<n;j++) chk |= gcd(a[j], i)==1; if(chk) { cout << i << '\n'; break; } } } } ```