题解：判断两个数的乘积是否为素数

题目分析

给定两个整数 $a$ 和 $b$，我们需要判断它们的乘积 $a \times b$ 是否为素数。

输入格式：

• 第一行是测试组数 $T$（$1 \leq T \leq 10$）
• 接下来 $T$ 行，每行包含两个整数 $a$ 和 $b$（$1 \leq a, b \leq 10^{11}$）

输出格式：

• 对于每组测试数据，如果 $a \times b$ 是素数，输出 YES，否则输出 NO

数学原理

素数的定义

素数（质数）是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

关键数学性质

定理：如果 $p = a \times b$ 是一个素数，那么 $a$ 和 $b$ 中必须有一个等于1，另一个等于该素数。

证明： 假设 $p = a \times b$ 是一个素数，且 $a > 1$，$b > 1$。

根据素数的定义，素数只有两个正因数：1和它本身。如果 $a > 1$ 且 $b > 1$，那么：

• $a$ 是 $p$ 的一个因数（因为 $p = a \times b$）
• $b$ 是 $p$ 的一个因数（因为 $p = a \times b$）
• 而且 $a \neq 1$，$a \neq p$（因为 $b > 1$，所以 $a < p$）
• 同理 $b \neq 1$，$b \neq p$

这意味着 $p$ 至少有四个不同的因数：1, $a$, $b$, $p$，这与素数的定义矛盾。因此，如果 $p = a \times b$ 是素数，那么 $a$ 和 $b$ 中必须有一个等于1。

推论

对于 $a \times b$ 是素数的必要条件：

1. $a = 1$ 且 $b$ 是素数，或者
2. $b = 1$ 且 $a$ 是素数

算法设计

基于上述数学原理，我们可以设计高效的算法：

1. 如果 $a = 1$，检查 $b$ 是否为素数
2. 如果 $b = 1$，检查 $a$ 是否为素数
3. 其他情况直接返回 NO

素数检测算法

由于 $a$ 和 $b$ 最大可达 $10^{11}$，我们需要高效的素数检测算法。

使用试除法优化：

• 先判断特殊情况（$n \leq 1$ 不是素数，$n = 2$ 是素数）
• 排除所有偶数（除了2）
• 只需要检查到 $\sqrt{n}$ 的因数
• 以步长2递增（只检查奇数因数）

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

bool isPrime(ll n) {
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    
    // 只需要检查到 sqrt(n)
    for (ll i = 3; i <= n / i; i += 2) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        ll a, b;
        cin >> a >> b;
        
        // 根据数学原理：a*b是素数当且仅当(a==1且b是素数)或(b==1且a是素数)
        if ((a == 1 && isPrime(b)) || (b == 1 && isPrime(a))) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    
    return 0;
}