牛牛与GCD题解

牛牛最近迷上了GCD(最大公约数)，好奇的他想知道在[1,n]整数区间中的所有整数对中(每个整数对中数都不同)，最大的GCD是多少？
只不过牛牛无法解决该问题，他打算求助于你，给定一个n，返回[1,n]整数区间中的所有整数对中最大的GCD。

这题如果我们暴力的去求解，时间复杂度上是不允许通过的。只不过我们可以去思考关于[1,n]所有整数对中最大的GCD是否包含某种规律，我们可以尝试着去归纳，例如：
n = 2 , MAX(GCD) = 1
n = 3 , MAX(GCD) = 1
n = 4 , MAX(GCD) = 2
n = 5 , MAX(GCD) = 2
那么规律显而易见了，n为奇数，答案为(n-1)/2,反之为n/2。
时间复杂度
空间复杂度
代码如下：

class Solution {
public:
    /**
     * 返回[1,n]整数区间中的所有整数对中最大的GCD。
     * @param n int整型 代表[1,n]整数区间的右边界
     * @return int整型
     */
    int solve(int n)
    {
        // write code here
        if (n % 2)
            n--; 
        return n / 2;
    }
};