There are two wooden sticks of lengths A and B respectively. Each of them can be cut into shorter sticks of integer lengths. Our goal is to construct the largest possible square. In order to do this, we want to cut the sticks in such a way as to achieve four sticks of the same length (note that there can be some leftover pieces). What is the longest side of the square that we can achieve?
Write a function:
class Solution {public int solution(int A, int B); }that, given two integers A and B, returns the side length of the largest square that we can obtain. If it is not possible to create any square, the function should return 0.
Examples:
- Given A = 10, B = 21, the function should return 7. We can split the second stick into three sticks of length 7 and shorten the first stick by 3.
- Given A = 13, B = 11, the function should return 5. We can cut two sticks of length 5 from each of the given sticks.
- Given A = 2, B = 1, the function should return 0. It is not possible to make any square from the given sticks.
- Given A = 1, B = 8, the function should return 2. We can cut stick B into four parts.
Write an efficient algorithm for the following assumptions:
- A and B are integers within the range [1..1,000,000,000].
这题的本质是判断用两根木棍 A 和 B 最多能切出多少条相同长度的边，并且要凑够 4 条边组成正方形。由于边长越大，需要的边数越少；边长越小，能切出的总段数越多，因此可以把“是否能组成 4 条”作为单调条件，用二分搜索在 [1, A+B] 中寻找最大的可行边长。判断某个长度 x 时，只需计算 A/x + B/x 是否至少为 4，注意使用 64 位整数避免溢出。最终返回最大的可行值；如果连 1 都不行，则返回 0。
