P4752 Divided Prime

题目描述

给定一个数字 AA ，这个 AA 由 a_1,a_2,\cdots,a_Na

1

​ ,a

2

​ ,⋯,a

N

​ 相乘得到。

给定一个数字 BB ，这个 BB 由 b_1,b_2,\cdots,b_Mb

1

​ ,b

2

​ ,⋯,b

M

​ 相乘得到。

如果 \frac{A}{B}

B

A

​ 是一个质数，请输出YES，否则输出NO。

输入输出格式

输入格式：

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

第一行输入两个整数 N,MN,M ，分别表示 AA 由 NN 个数字相乘得到， BB 由 MM 个数字相乘得到。

第二行输入 NN 个整数，分别表示组成 AA 的 NN 个数字。

第三行输入 MM 个整数，分别表示组成 BB 的 MM 个数字。

保证对于一个数字，其在 {b_i}b

i

​ 中出现的次数不多于在 {a_i}a

i

​ 中出现的次数。

输出格式：

对于每组数据：

如果 \frac{A}{B}

B

A

​ 是一个质数，请输出YES，否则输出NO。

在输出YES或NO后输出一个换行符。

---

模拟 + 数学

首先读题可知，分母\(B\)的因子分子\(A\)都有，所以我们把因子排序，双指针模拟约分的过程。

一个约分后的分数为质数，当且约分后分子剩余一个质数

所以我们约分，当分子有合数不能约分是，则不是质数，或者当分子有两个以上质数无法约分是则不是质数

注意\(1\)不是质数，还有分子分母约数的\(1\)要跳过

Code

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           typedef long long LL;using namespace std;LL RD(){ LL out = 0,flag = 1;char c = getchar(); while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();} while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();} return flag * out; }const LL maxn = 1000019;LL T, na, nb;LL a[maxn], b[maxn];bool isprime(LL x){ LL R = sqrt(x * 1.0); for(LL i = 2;i <= R;i++){ if(x % i == 0)return 0; } return 1; }int main(){ T = RD(); while(T--){ memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b)); na = RD();nb = RD(); for(LL i = 1;i <= na;i++)a[i] = RD(); for(LL i = 1;i <= nb;i++)b[i] = RD(); sort(a + 1, a + 1 + na);sort(b + 1, b + 1 + nb); LL p1 = 1, p2 = 1, tot = 0, mem = -1; bool flag = 1; while(a[p1] == 1)p1++;while(b[p2] == 1)p2++; while(p1 <= na){ if(a[p1] == b[p2])p1++, p2++; else{ mem = a[p1]; if(!isprime(mem)){ printf("NO\n"); flag = 0; break; } tot++; if(tot == 2){ printf("NO\n"); flag = 0; break; } p1++; } } if(mem == -1){ printf("NO\n"); continue; } if(flag) printf("YES\n"); } return 0; }