喵~ 各位好呀！今天本猫娘要给大家带来一道非常有趣的题目，Codeforces 上的 1165D - Almost All Divisors。这道题就像一个猜数字的小游戏，需要我们运用一点点关于约数的小智慧来解决它。一起来看看吧！

题目大意

这道题是这样滴：有一个神秘的整数 x，我们不知道它是多少。但是呢，有人给了我们一个列表，里面包含了 x 的几乎所有约数。

“几乎所有”是什么意思呢？就是说这个列表里有 x 的全部约数，唯独少了 1 和 x 本身。

我们的任务就是，根据这个给定的约数列表，找出最小的那个可能的 x。如果给定的列表有问题，根本不可能存在这样的 x，那我们就得告诉他“办不到啦！”，输出 -1 就好啦，喵~

举个栗子： 如果给我们的列表是 [8, 2, 12, 6, 4, 24, 16, 3]，这些是数字 48 的所有约数（除了1和48）。所以我们应该输出 48。 如果列表是 [2]，那么 x 可能是 4（因为4的约数是1, 2, 4，去掉1和4就剩2了），所以输出 4。

解题方法

拿到这个问题，咱的猫猫脑袋瓜要开始转动啦！(ฅ'ω'ฅ)

一个整数 x 的约数们其实是成双成对出现的。如果 d 是 x 的一个约数，那么 x / d 也一定是 x 的约数。比如说，12 的约数有 (1, 12), (2, 6), (3, 4)，你看，它们都是一对一对的。

题目给的列表，是 x 除了 1 和 x 之外的所有约数。那么，这个列表里最小的数，一定是 x 的最小质因数。而列表里最大的数，一定是 x 除以它最小质因数的结果。

所以，一个非常重要的猜想就诞生了：我们把给定的约数列表排个序，取最小的那个数 d_min 和最大的那个数 d_max，它们俩的乘积 d_min * d_max，就很可能是我们想要的 x！

为什么呢？因为最小的约数（非1）和最大的约数（非x）肯定是一对儿呀！它们的乘积理应等于 x。

所以，我们的候选答案 candidate_x 就等于 d_min * d_max。

但是！光猜出来可不行，我们还得检查一下才安心喵。万一给定的列表是骗人的怎么办？所以，验证步骤是必不可少的：

1. 找出候选 x：将输入的 n 个约数排序，candidate_x = d[0] * d[n-1]。
2. 找出候选 x 的所有约数：我们自己动手，把 candidate_x 的所有约数（不包括1和它自己）都找出来。
3. 比对：把我们自己找出来的约数列表，和题目给的约数列表进行比较。
   • 如果两个列表一模一样（数量相同，每个数字也相同），那说明我们的猜想是正确的！candidate_x 就是答案。
   • 如果两个列表不一样，那就说明题目给的列表是矛盾的，根本不存在这样的 x。这时就输出 -1。

这样一来，问题就迎刃而解啦！是不是很简单呢？

题解代码

下面是解题的 C++ 代码，本猫娘加上了一些注释，方便大家理解喵~

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

// 这个函数用来解决单个查询喵
void solve() {
    int n;
    std::cin >> n;
    std::vector<long long> d(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> d[i];
    }

    // 先把主人的数字们排个队喵~ 这样就能轻松找到最小和最大的数
    std::sort(d.begin(), d.end());

    // 如果存在一个数 x，那么它的最小约数（非1）和最大约数（非x）
    // 一定是 d[0] 和 d[n-1]。
    // 根据约数的配对性质，最小的 d[0] 和最大的 d[n-1] 应该是一对。
    // 所以，我们唯一可能的候选 x 就是它们的乘积啦。
    long long candidate_x = d[0] * d[n - 1];

    // 接下来，就是最重要的验证环节！
    // 我们来找出 candidate_x 的所有约数（除了1和它自己）。
    std::vector<long long> generated_divs;
    for (long long i = 2; i * i <= candidate_x; ++i) {
        if (candidate_x % i == 0) {
            generated_divs.push_back(i);
            // 如果 i*i 不等于 candidate_x，说明 i 和 candidate_x/i 是不同的一对约数
            if (i * i != candidate_x) {
                generated_divs.push_back(candidate_x / i);
            }
        }
    }
    
    // 把我们生成的约数也排个序，方便和输入的列表比较
    std::sort(generated_divs.begin(), generated_divs.end());

    // 现在，只要比较我们生成的约数列表和输入的列表是否完全一样就行啦。
    // std::vector 的 `==` 操作符会比较大小和所有元素，非常方便！
    if (d == generated_divs) {
        std::cout << candidate_x << "\n";
    } else {
        std::cout << -1 << "\n";
    }
}

int main() {
    // 加上这个可以让输入输出更快哦，是竞赛小技巧~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

猫猫小课堂：相关知识点

最后是猫猫小课堂时间！我们来复习一下这道题用到的知识点吧~

1. 约数（Divisor）

也叫因数。如果一个整数 a 可以被另一个整数 b 整除（也就是 a % b == 0），那么 b 就是 a 的一个约数。

• 例子：12 的约数有 1, 2, 3, 4, 6, 12。

2. 约数的性质

• 1 是任何正整数的约数。
• 任何正整数 x 都是它自己的约数。
• 配对性质：这是一个非常重要的性质！一个非平方数 x 的所有约数都是成对出现的。如果 d 是 x 的约数，那么 x/d 也是。这对我们解题的启发是：x 的最小约数（非1）和最大约数（非x）的乘积，正好就是 x 本身。

3. 如何高效地找出一个数的所有约数

想找出一个数 N 的所有约数，我们不需要从 1 一直检查到 N，那样太慢啦！有一个 O(sqrt(N)) 的高效算法：

我们只需要从 i = 1 遍历到 sqrt(N)。

• 如果 i 能整除 N（即 N % i == 0），那么 i 就是一个约数。
• 同时，N / i 也一定是一个约数。
• 注意：如果 N 是一个完全平方数（比如 36），当 i = sqrt(N) (比如 i=6) 时，i 和 N/i 是同一个数，我们只记录一次就好啦。

在本题中，因为我们不需要 1 和 x，所以循环可以从 2 开始。

好啦，今天的题解就到这里啦！希望大家都能明白其中的奥妙。如果还有什么问题，随时可以来问本猫娘哦！下次见，喵~ (ฅ'ω'ฅ)