Divided Prime

题目描述

给定一个数字$A$，这个$A$由$a_1,a_2,\cdots ,a_N$相乘得到。

给定一个数字$B$，这个$B$由$b_1,b_2,\cdots ,b_M$相乘得到。

如果$\frac{A}{B}$是一个质数，请输出YES，否则输出NO。

输入格式

每个测试点包含多组数据，第一行读入一个整数 $T$ 表示数据组数，对于每组数据：

第一行输入两个整数 $N,M$，分别表示 $A$ 由 $N$ 个数字相乘得到，$B$ 由 $M$ 个数字相乘得到。

第二行输入 $N$ 个整数，分别表示组成 $A$ 的 $N$ 个数字。

第三行输入 $M$ 个整数，分别表示组成 $B$ 的 $M$ 个数字。

保证对于一个数字，其在 $b_i$ 中出现的次数不多于在 $a_i$ 中出现的次数。

输出格式

对于每组数据：
如果 $\frac{A}{B}$ 是一个质数，请输出 YES，否则输出 NO。
在输出 YES 或 NO 后输出一个换行符。

样例 #1

样例输入 #1

2
3 2
5 7 7
5 7
4 2
5 7 7 7
5 7
1
2
3
4
5
6
7

样例输出 #1

YES
NO
1
2

提示

$1\le N\le 100000$

$0\le M\le N$

$1\le a_i,b_i\le 10^{12}$

$1\le T\le 10$

$\sum N\le 100000$

分析

保证对于一个数字，其在bi中出现的次数不多于在ai中出现的次数。

根据这句话，我们不难得出：

1. 如果x在a中没有出现，那么x在b中一定没有出现。
2. 如果x在b中出现，那么x在a中一定出现。

因为a中乘积一定整除b中乘积，而如果m-n大于1，或者m==n时，剩下的乘积一定都不是质数；所以只需要看在a中多出来的数字就行啦。

怎么看在a中多出来的数字呢？

其实也不难，首先因为多出来的最多只有一个，所以我们可以在b末尾加一个-1000。
接着对两个数组分别排序，a中第一个与b不对应的那个数字就是多出来的数字。
最后判断其是否为素数即可！

注意
因为1对于乘积没有什么影响，所以我们要滤掉读入里面所有的1（当然也可以不过滤）

代码

#include

using namespace std;

int n,m;

int a[1000000],b[1000000];

bool aa(int n)//判断质数 
{
	for(int i=2;i<=n/i;i++)
	{
		if(n%i==0)
		{
			return 0;
		}
	}
	
	return 1;
}

int T;

int main()
{
	cin>>T;
	
	while(T--)
	{
		cin>>m>>n;
	
		for(int i=1;i<=m;i++)
		{
			cin>>a[i];
			
			if(a[i]==1)//过滤
			{
				i--;
				
				m--;
			}
		}
		
		for(int i=1;i<=n;i++)
		{
			cin>>b[i];
			
			if(b[i]==1)
			{
				i--;
				
				n--;
			}
		}
		
		if(m-n==0||m-n>1)
		{
			cout<<"NO"<<endl;
			
			continue;
		}
		
		sort(a+1,a+m+1);//排序
		sort(b+1,b+n+1);
		
		b[m]=-1000;//赋值
		
		for(int i=1;i<=m;i++)
		{
			if(a[i]!=b[i])//多出来的那个数
			{
				if(aa(a[i])==1)//判断是质数还是合数
				{
					cout<<"YES"<<endl;
				}
				else
				{
					cout<<"NO"<<endl;
				}
				
				break;//退出循环
			}
		}
	}
	
	return 0;
}
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
84
85
86
87

结束啦~