爱吃素时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述牛妹是一个爱吃素的小女孩所以很多素数都害怕被她吃掉。一天两个数字a aa和b bb为了防止被吃掉决定和彼此相乘在一起这样被吃掉的风险就会大大降低但仍有一定的可能被吃掉请你判断他们相乘后是否仍有被吃掉的风险。也就是说请你判断a × b a×ba×b是否是素数。素数是指大于11的正整数中有且仅有两个因子的数。输入描述输入第一行是一个整数T ( 1 ≤ T ≤ 10 ) T(1≤T≤10)T(1≤T≤10)表示测试组数。接下来T TT行每一行两个整数a , b ( 1 ≤ a , b ≤ 10 11 ) a,b(1≤a,b≤10^{11})a,b(1≤a,b≤1011)。输出描述对于每一行输入若输入满足a × b a×ba×b是素数输出一行 Y E S YESYES否则输出一行 N O NONO没有引号。示例1输入3 2 3 1 7 1 4输出NO YES NO解题思路本题核心是数论性质推导利用质数定义直接简化判断逻辑无需计算超大数乘积。根据质数的定义两个正整数相乘结果为质数的唯一条件其中一个数必须是1 11另一个数必须是质数若两个数均大于1 11乘积一定是合数直接判定不成立。输入数据范围达10 11 10^{11}1011直接相乘会溢出因此仅需判断是否含数字1 11再对另一个数用试除法判定质数即可。算法时间复杂度极低完美规避数值溢出问题适配题目所有测试约束。总结核心逻辑乘积为质数 ⇔ 一个数是1另一个数是质数两数均1则直接不成立。关键操作判断输入是否包含1、试除法判定质数、避免大数乘法溢出。效率保障数论结论简化计算试除法高效验证无冗余运算。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;booljudge(ll num){ll limitsqrt(num);if(num2)returnfalse;for(ll i2;ilimit;i){if(num%i0)returnfalse;}returntrue;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll t;cint;while(t--){ll a,b;cinab;if(a1||b1){ll resa*b;if(judge(res))coutYESendl;elsecoutNOendl;}elsecoutNOendl;}return0;}