C++11 解決最大完全平方数乘积问题

题目背景

若一个数能表示成某个整数的平方的形式，则称这个数为完全平方数。

注意：完全平方数是非负数。

题目描述

给出一个正整数 n ，从 1,2,…,n 中选出若干个数，使得它们的乘积是完全平方数。

求此乘积最大是多少。

解题思路：

根据数学定理，一个数能够表示成完全平方数的形式，即为该数的所有质因数的指数均为偶数。

因此，我们需要将给定的整数 n 进行质因数分解，然后找出所有质因数的指数中的最小偶数。

具体步骤如下：

对整数 n 进行质因数分解。
统计每个质因数的指数的奇偶性。
将偶数指数的质因数相乘，得到乘积为完全平方数的最大值。

C++11代码实现：

#include <iostream>
#include <vector>

using namespace std;

// 判断一个数是否为完全平方数
boolean isPerfectSquare(int num) {
    int root = sqrt(num);
    return root * root == num;
}

// 质因数分解
vector<int> primeFactors(int n) {
    vector<int> factors;
    for (int i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            factors.push_back(i);
            n /= i;
        }
    }
    if (n > 1) {
        factors.push_back(n);
    }
    return factors;
}

int main() {
    int n;
    cin >> n;

    vector<int> factors = primeFactors(n);
    vector<int> exponents;

    for (int i = 0; i < factors.size(); i++) {
        int count = 0;
        while (i < factors.size() && factors[i] == factors[i + 1]) {
            count++;
            i++;
        }
        exponents.push_back(count + 1);
    }

    int result = 1;
    for (int i = 0; i < exponents.size(); i++) {
        if (exponents[i] % 2 == 0) {
            result *= pow(factors[i], exponents[i]);
        }
    }

    cout << result << endl;

    return 0;
}

时间复杂度分析：

质因数分解的时间复杂度为 O(sqrt(n))，统计质因数指数的时间复杂度为 O(log(n))，计算乘积的时间复杂度为 O(m)，其中 m 为指数为偶数的质因数的个数。所以总的时间复杂度为 O(sqrt(n) + log(n) + m)。