【Leetcode】1362. Closest Divisors（配数学证明）

题目地址：

https://leetcode.com/problems/closest-divisors/

给定一个正整数$x$，要求找到$a,b$满足$ab=x+1\vee ab=x+2$，并且使得$|a-b|$尽可能小。

可以证明解是唯一的。不妨设$a_1\le b_1,a_2\le b_2$如果$a_1{b}_1=x+1,a_2{b}_2=x+2$并且$b_1-a_1=b_2-a_2$，那么$a_2-a_1=b_2-b_1$，则$a_2{b}_2\ge (a_1+1)(b_1+1)=a_1{b}_1+a_1+b_1+1\ge a_1{b}_1+3=x+4$，矛盾。

接着从$\sqrt{x+2}\to 1$遍历，枚举$a$，如果发现$a|(x+1)$或者$a|(x+2)$，则找到了一组解。这个解就是最优解。因为$(x+1,x+2)=1$，所以上面的两个整除式子不能同时成立。如果发现$a_1{b}_1=x+1,a_2{b}_2=x+2,a_2<a_1$，由于$a_2{b}_2>a_1{b}_1$所以$b_2>b_1$，矛盾；如果发现$a_1{b}_1=x+2,a_2{b}_2=x+1,a_2<a_1$，如果$b_2<b_1$，则$a_1{b}_1=x+2\ge (a_2+1)(b_2+1)\ge x+4$矛盾。

代码如下：

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

    return {};
  }
};
1
2
3
4
5
6
7
8
9
10
11

时间复杂度$O(\sqrt{x})$，空间$O(1)$。