本蒟蒻的第六篇题解，求管理员通过。
正题
题意
对于每组测试数据：
给定一个长度为 \(n\) 的数组 \(a_n\)，求一个最小的整数 \(x\) 使得能找到一个 \(a_i\) 满足 \(\gcd(a_i,x)=1\)。
分析
暴力思路：直接从 \(1\) 开始一直枚举，直到找到满足题干条件的数输出。
结果——竟然 AC 了！所以这题是不是红题。
优化思路 1：可以对 \(\{a_n\}\) 中所有的数求最大公约数，这样就可以省略从下标 \(1\) 枚举到 \(n\) 的动作，时间复杂度大大降低。
然而——还可以优化：
优化思路 2：从小到大枚举质数即可。又注意到
\[2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 \times 23 \times 29 \times 31 \times 37 \times 41 \times 43 \times 47 \times 53 > 10^{18}
\]
故最多只用枚举到 \(53\) 即可。
正确性说明：因为如果存在一个合数 \(o\) 使得 \(\gcd(a_i,o)=1\)，则这个合数在分解质因数后的质因子 \(p\) 也会使得 \(\gcd(a_i,p)=1\)，所以枚举质数就可以了。
code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <iterator>
#include <map>
#include <unordered_map>
#include <queue>
#include <string>
#include <cstring>
#include <set>
#include <bitset>
#include <unordered_set>
#include <vector>
#include <deque>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <list>
#include <array>
#include <iterator>
#include <cmath>
#include <new>
#include <random>
#include <cfloat>
#include <cstdlib>
#include <climits>
#include <numeric>
#include <complex>
#include <ctime>
#include <chrono>
#include <thread>
#include <mutex>
#include <future>
#include <exception>
#include <stdexcept>
#include <cstdint>
#include <cassert>
#include <stack>
#include <cctype>
#define Ofile(s) freopen(s".in", "r", stdin), freopen (s".out", "w", stdout)
#define Cfile(s) fclose(stdin), fclose(stdout)
#define fast ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define maxn 1000005
#define maxm 55//好习惯
#define int long long//强调那么多遍，总有人忘记
#define inf 2147483647
using namespace std;int t, n, sum;int a[maxn], prime[maxm];bool isprime(int x) {if (x <= 1)return false;for (int i = 2; i * i <= x; i++)if (x % i == 0)return false;return true;
}void init() {for (int i = 2; i <= 53; i++)if (isprime(i))prime[++sum] = i;//预处理
}int getgcdsum() {int gcc = a[1];for (int i = 2; i <= n; i++)gcc = __gcd(gcc, a[i]);return gcc;//全数列的大公因
}signed main() {
#ifndef ONLINE_JUDGE// Ofile("");// Cfile("");
#endifinit();cin >> t;while (t--) {cin >> n;fill(a + 1, a + n + 1, 0);for (int i = 1; i <= n; i++)cin >> a[i];int minn = inf, gcc = getgcdsum();for (int i = 1; i <= sum; i++)if (__gcd(gcc, prime[i]) == 1)minn = min(minn, prime[i]);//枚举if (minn == inf)cout << -1 << endl;//记得换行else cout << minn << endl;}return 0;
}