CF1165D
题意
多组输入t
对于每个输入,给你一个n,给你一个长度为n的序列a.问是否存在一个数,他的所有约数(除了1和它本身),都在这个序列中.
如果有,输出满足条件的最小的数,如果没有,则输出-1
$1<=n<=300$
$2<=a_i<=1e6$
思路
思路很简单,对a数组排序,则约数x如果存在就是a[0]*a[n-1]
那么问题就变成了如何判断x的约数都在集合中.
最开始想的比较朴素,直接就暴力($O(\sqrt{x})$)求出x的所有约数,然后排序去重,和a数组比较.
我感觉理论上是可以过的.因为x最大是1e12,设约数总共c个,总复杂度是O(t*(1e6+300*log300+c*logc))考虑到c不会很大,所以复杂度应该是没有问题的.但是确实是t了
那就换个思路:验证数组a是不是x的所有约数
首先先验证大小上对不对:欧拉筛+唯一分解定理,利用公式求出x的约数的个数,然后减2,判断是否等于n,如果不相等则输出-1
如果相等,则将a数组加入set集合,然后x扫描a数组,判断 if (x % d[i] != 0 || !s.count(x / d[i])) 这里第一次写错了.不仅需要判断d[i]是否是x的约数,还要判断x/d[i]是否也在集合中.
综上所述,此题解决.
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>
using namespace std;
#define maxn 3000
#define maxm 100000 + 10
#define ll long long
#define endl '\n'
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
ll d[maxn];
set<ll> s;
const int N = 1000000 + 10;
bool prime[N]; // prime[i]表示i是不是质数
int p[N];
ll tot;
void init() { // 线性筛,每个数只会被筛掉一次
tot = 0ll;
for (int i = 2; i < N; i++)
prime[i] = true; //初始化为质数
for (int i = 2; i < N; i++) {
if (prime[i])
p[tot++] = i; //把质数存起来
for (int j = 0; j < tot && i * p[j] < N; j++) {
prime[i * p[j]] = false;
if (i % p[j] == 0)
break; //保证每个合数被它最小的质因数筛去
}
}
}
vector<pair<ll, ll>> v;
ll CntPrime(ll n) {
int ans = 1;
for (int i = 0; i < tot && p[i] * 1ll * p[i] <= n; ++i) {
if (n % p[i] == 0) {
int cnt = 0;
while (n % p[i] == 0) {
n /= p[i];
++cnt;
}
ans *= (1 + cnt);
}
}
if (n > 1) {
ans *= 2;
}
return ans;
}
int main() {
ios::sync_with_stdio(0);
init();
int T;
cin >> T;
while (T--) {
s.clear();
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> d[i];
s.insert(d[i]);
}
sort(d, d + n);
ll x = d[0] * d[n - 1];
bool flag = 0;
ll ans = CntPrime(x) - 2;
if (ans == n) {
for (int i = 0; i < n; ++i) {
if (x % d[i] != 0 || !s.count(x / d[i])) {
flag = 1;
break;
}
}
if (flag) {
cout << -1 << endl;
} else {
cout << x << endl;
}
} else {
cout << -1 << endl;
}
}
return 0;
}
