C++ 算法：求集合中互为倍数的子集数量

问题描述： 米小游拿到了一个集合（集合中元素互不相等）。她想知道，该集合有多少个元素数量大于 1 的子集，满足子集内的元素两两之间互为倍数关系？由于数量可能过大，请对 (10 的九次方 + 7) 取模。

输入描述： 第一行输入一个正整数 n，代表集合大小。第二行输入几个正整数 ai，代表集合的元素。 1 ≤ n ≤ 10 的五次方 1 ≤ ai ≤ 10 的六次方

输出描述： 一个整数，代表满足题意的子集数量对对 10⁹ + 7 取模的值。

算法思路：

首先，我们可以对集合中的每个元素进行分解质因数，得到每个元素的质因数分解式。

对于一个子集，如果子集中有两个元素的质因数分解式不一致，那么这个子集一定不符合条件。因此，我们可以考虑枚举子集的最小公共质因数，然后判断子集中的所有元素是否都能被这个最小公共质因数整除。如果能，那么这个子集就符合条件。

具体来说，我们可以对集合中每个元素的质因数分解式进行合并，得到这个集合的最小公共质因数的质因数分解式。然后，我们枚举所有的最小公共质因数，对于每个最小公共质因数，我们统计有多少个元素能被它整除，然后根据组合数学的知识，计算出对应的子集数量。

最后，将所有符合条件的子集数量累加起来，就是最终的答案。

时间复杂度

对于每个元素，需要将它的质因数分解式合并，时间复杂度是 O(log a_i)。枚举最小公共质因数的时间复杂度是 O(max(a_i) log(max(a_i)))。计算组合数的时间复杂度是 O(n)。因此，总时间复杂度是 O(n log a_i + a_max log a_max)。

空间复杂度

需要用哈希表存储每个元素的质因数分解式，空间复杂度是 O(n log a_i)。

C++ 代码

#include <iostream>
#include <vector>
#include <unordered_map>
#define MOD 1000000007

using namespace std;

// 计算组合数 C(n, k)
long long C(long long n, long long k) {
    if (k > n) {
        return 0;
    }
    long long result = 1;
    for (long long i = 1; i <= k; i++) {
        result = (result * (n - i + 1)) % MOD;
        result = (result * modInverse(i, MOD)) % MOD;
    }
    return result;
}

// 计算模逆元
long long modInverse(long long a, long long m) {
    long long m0 = m, t, q;
    long long x0 = 0, x1 = 1;

    if (m == 1)
        return 0;

    while (a > 1) {
        q = a / m;
        t = m;
        m = a % m;
        a = t;
        t = x0;
        x0 = x1 - q * x0;
        x1 = t;
    }

    if (x1 < 0)
        x1 += m0;

    return x1;
}

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // 对每个元素进行质因数分解
    unordered_map<long long, long long> primeFactors;
    for (int i = 0; i < n; i++) {
        long long num = a[i];
        for (long long j = 2; j * j <= num; j++) {
            while (num % j == 0) {
                primeFactors[j]++;
                num /= j;
            }
        }
        if (num > 1) {
            primeFactors[num]++;
        }
    }

    // 统计每个最小公倍数对应的子集数量
    long long count = 0;
    for (auto it = primeFactors.begin(); it != primeFactors.end(); it++) {
        long long commonFactor = it->first;
        long long numElements = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] % commonFactor == 0) {
                numElements++;
            }
        }
        // 计算满足条件的子集数量
        count = (count + C(numElements, 2)) % MOD;
    }

    cout << count << endl;
    return 0;
}