题目描述

给你一个整数 num，找出差绝对值最小的两个数，满足乘积等于 num + 1 或 num + 2。

你可以按任意顺序返回这两个整数。

样例

输入：num = 8
输出：[3,3]
解释：
对于 num + 1 = 9，最接近的两个因数是 3 和 3；
对于 num + 2 = 10, 最接近的两个因数是 2 和 5，因此返回 3 和 3 。

输入：num = 123
输出：[5,25]

输入：num = 999
输出：[40,25]

限制

• 1 <= num <= 10^9

算法

(暴力枚举，数学) $O(\sqrt{n})$

1. 分别求 num + 1 和 num + 2 的答案。
2. 暴力枚举约数，根据基础数论知识，约数只需要枚举到平方根，且约接近平方根的两个数的乘积，差值越小。

时间复杂度

• 最多有 $O(\sqrt{n})$ 个约数，故总时间复杂度为 $O(\sqrt{n})$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    vector<int> calc(int num) {
        for (int i = ceil(sqrt(num)) + 1; i >= 1; i--)
            if (num % i == 0)
                return {i, num / i};

        return {1, num};
    }

    vector<int> closestDivisors(int num) {
        vector<int> ans1(calc(num + 1)), ans2(calc(num + 2));

        if (abs(ans1[0] - ans1[1]) < abs(ans2[0] - ans2[1]))
            return ans1;

        return ans2;
    }
};