C++ 编程实现：计算集合中满足倍数关系的子集数量

#include #include using namespace std;

const int MOD = 1e9 + 7;

vector divisors(int n) { // 求 n 的所有因子 vector res; for (int i = 1; i * i <= n; i++) { if (n % i == 0) { res.push_back(i); if (i != n / i) { res.push_back(n / i); } } } return res; }

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

vector<int> cnt(1e6 + 1); // cnt[i] 表示集合中元素等于 i 的个数
for (int x : a) {
    cnt[x]++;
}

vector<int> dp(1e6 + 1, 1); // dp[i] 表示以 i 为倍数的子集数量
for (int i = 1e6; i >= 1; i--) {
    vector<int> divs = divisors(i); // 求 i 的所有因子
    for (int d : divs) {
        dp[d] = (dp[d] + dp[i]) % MOD; // 更新以 d 为倍数的子集数量
    }
}

int ans = 0;
for (int i = 1; i <= 1e6; i++) {
    if (cnt[i] >= 2) { // 集合中元素等于 i 的个数大于等于 2
        ans = (ans + dp[i] - 1 + MOD) % MOD; // 减去空集的情况
    }
}
cout << ans << endl;

return 0;

}