洛谷2018-7月月赛

U29473

【题目链接】

　　　　https://www.luogu.org/problemnew/show/U27076

【算法】

　　　　我的算法比较渣，最多n=1e5个数，于是离散化，记录每个数出现次数。

　　　　然后判断是否是质数，每个数范围为1~1e12于是只需判断是否能能被1~1e6范围内且小于它的1/2次方的质数整除即可，所以打了一个1~1e6的质数表。

　　　　看了标程自己是个zz，根号ai不超过1e6，没必要大表，不过快一点。。。。而且，排个序判断下就好，实乃水题，溜了，我太渣。。。。

【注意】

　　　　stl::unique() 函数如果需要计算重复数字的话尽量不要用。。。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 1e6+10;
 4 typedef long long ll;
 5 vector<int> a;
 6 bool is_prime[maxn];
 7 int t,m,n,tot;
 8 ll b[100010],c[100010];
 9 int d[100010];
10 void prime()
11 {
12     is_prime[2] = true;
13     for(int i = 3; i < maxn; i += 2)
14         is_prime[i] = true;
15     for(int i = 3; i < sqrt(maxn+0.1); i++) {
16         if(is_prime[i]) {
17             for(int j = i*i; j < maxn; j += 2 * i)
18                 is_prime[j] = false;
19         }
20     }
21     for(int i = 2; i < maxn; i++) if(is_prime[i]) a.push_back(i);
22 }
23 void discrete()
24 {
25     sort(b+1,b+n+1);
26     for(int i = 1; i <= n; i++) {
27         if(b[i] != b[i-1]) c[++tot] = b[i];
28         d[tot]++;
29     }
30 }
31 int query(ll x)
32 {
33     return lower_bound(c+1,c+tot+1,x) - c;
34 }
35 int main()
36 {
37     prime();
38     cin>>t;
39     while(t--) {
40         memset(d,0,sizeof(d));
41         tot = 0;
42         cin>>n>>m;
43         for(int i = 1; i <= n; i++) {
44             cin>>b[i];
45         }
46         discrete();
47         for(int i = 1; i <= m; i++) {
48             ll cur;
49             cin>>cur;
50             d[query(cur)]--;
51         }
52 
53         ll times=0, rec=0;
54         for(int i = 1; i <= tot; i++) {
55             if(d[i] > 0 && c[i] != 1) {
56                 times += d[i];
57                 rec = c[i];
58             }
59         }
60         if(times != 1)
61             cout<<"NO"<<endl;
62         else {
63             bool flag = true;
64             for(int i = 0; a[i] <= sqrt(rec+1.0) && i < a.size(); i++)
65                 if(rec % a[i] == 0) { flag = false; break; }
66             if(flag) cout<<"YES"<<endl;
67             else cout<<"NO"<<endl;
68         }
69     }
70     return 0;
71 }