P4710 满足条件的等式（入门）

解题思路

这道题要我们统计：集合中有多少个数，恰好等于集合中另外两个数的乘积。

先看个生活例子：假如我们有数字卡片 2、3、4、5、6。哪两个数相乘，结果还能在卡片里找到？2×3=6，而 6 也在卡片里，所以 6 就算一个"合格的数"。

做法很直接，分三步：

1. 先把所有数读进来，用一个 bool 数组 inSet 记录"某个数值是否在集合中"。这样判断一个数在不在集合里只需要 O(1) 的时间，非常快。
2. 用两层循环枚举任意两个不同的数 a[i] 和 a[j]，算出它们的乘积 p。
3. 如果 p 在集合中（inSet[p] 为真），而且这个 p 还没有被统计过（ok[p] 为假），就把它记下来，答案加一。

有两个细节要注意：

• 题目说的是"另外两个数"，所以不能拿同一个数自己乘自己。循环里我们规定 j 从 i+1 开始，保证 i、j 是两个不同位置上的数。集合里的数互不相同，所以不同位置就代表不同的数。
• 同一个乘积可能由好几组数得到，比如 24=3×8=4×6。题目数的是"有多少个不同的数"，所以要用 ok 数组去重，一个乘积只算一次。

边界情况：当两个数相乘的乘积非常大（比如超过 10000），它不可能出现在集合中，直接跳过判断即可。由于集合中的元素都小于 10000，我们只需要处理 p<10005 的情况。

参考代码

// 满足条件的等式：统计集合中有多少个数等于另外两个数之积
#include <iostream>
using namespace std;
int a[105];          // 存储集合中的数
bool inSet[10005];   // 某个数值是否在集合中
bool ok[10005];      // 该乘积是否已经计数过
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        inSet[a[i]] = true;
    }
    int ans = 0;
    // 枚举任意两个不同的数
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            long long p = (long long)a[i] * a[j];
            // 乘积不超过数据范围且该乘积在集合中，且没统计过
            if (p < 10005 && inSet[p] && !ok[p]) {
                ok[p] = true;
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

复杂度分析

两层循环枚举所有数对，一共要做 n(n-1)/2 次判断，所以时间复杂度是 O(n²)。题目中 n≤100，最坏也只有大约 5000 次判断，运行速度非常快。

空间方面，用了一个长度为 105 的 int 数组存集合，还有两个长度为 10005 的 bool 数组分别记录"数值是否在集合中"和"乘积是否统计过"，都属于常数级别的空间，与 n 的大小无关。