极简题解|吃素的小Z
2025-01-21 11:43:51
发布于:江苏
6阅读
0回复
0点赞
时间限制:1.00s
内存限制:128MB
题目描述
Z是一个爱吃素的大学生,所以很多素数都害怕被他吃掉。一天,两个数字a和b为了防止被吃掉,决定和彼此相乘在一起,这样被吃掉的风险就会大大降低,但仍有一定的可能被吃掉,请判断他们相乘后是否仍有被吃掉的风险。也就是说,请你判断a×b是否是素数。
素数是指大于1的正整数中,有且仅有两个因子的数。
输入格式
输入第一行是一个整数T(1≤T≤10),表示测试组数。
接下来T行,每一行两个整数a,b(1≤a,b≤1e11))。
首先判断a,b的特殊情况:a,b同(不)为1,如果是乘积要么是1要么包含1,a,b,本身4个因数。
然后判断其中一个不为1的数是否为素数
为了优化代码可以先判断a是否是1,如果是就a=b,b=1
接下来就只用判断a是不是质数
循环条件可以写j*j<=a,因为等价于j<=sqrt(a)还不用导入头文件速度也快
重中之重:a,b一定要开long long,本人没开结果一直有两个点TLE还不知道哪错了
#include<iostream>
using namespace std;
long long t,a,b;
bool l;
int main(){
cin>>t;
for(int i=0;i<t;i++){
cin>>a>>b;
if((a==1 && b==1)||(a!=1 && b!=1)){
cout<<"NO"<<endl;
continue;
}
if(a==1){
a=b;
b=1;
}
for(int j=2;j*j<=a;j++){
if(a%j==0){
l=1;
cout<<"NO"<<endl;
break;
}
}
if(l){
l=0;
}else{
cout<<"YES"<<endl;
}
}
}
这里空空如也
有帮助,赞一个