HDU 1796：容斥原理求小於 N 且能被集合中任意整數整除的數個數

問題描述

給定 N 和 M 個互不相同的正整數集合，求有多少小於 N 的正整數能被集合中至少一個數整除。N < 2³¹, M ≤ 10。

容斥原理公式

設集合元素為 a₁, a₂, ..., aₖ（去除 0 後）。答案 = Σ(-1)ⁱ⁺¹ × ⌊(N-1)/LCM(選取的 i 個元素)⌋，i 從 1 到 k。

DFS 枚舉所有非空子集

void dfs(int x, int ans, int now) { // x: 當前考慮元素, ans: 目標選取數, now: 已選數
    if (now == ans) {
        int l = 1;
        for (int i = 1; i <= k; ++i) if (vis[i]) l = lcm(l, s[i]);
        if (ans & 1) sum += (n-1)/l; else sum -= (n-1)/l;
        return;
    }
    for (; x <= k; ++x) if (!vis[x]) {
        vis[x] = 1; dfs(x+1, ans, now+1); vis[x] = 0;
    }
}

關鍵細節

• 輸入可能包含 0，需過濾（0 不能作除數）。
• LCM 計算用 a / gcd(a,b) * b 防溢出，數據範圍內 64 位足夠。
• M ≤ 10，子集總數 2¹⁰-1 = 1023，DFS 完全可行。
• 樣例：N=12, {2,3} → 2,3,4,6,8,9,10 共 7 個。

完整代碼

#include 
#include 
int s[27], vis[27], n, m, k, sum;
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }
int lcm(int a, int b) { return a / gcd(a,b) * b; }
// dfs 函數見上
int main() {
    while (scanf("%d%d", &n, &m) != EOF) {
        k = 0; sum = 0;
        for (int i = 1, a; i <= m; ++i) {
            scanf("%d", &a); if (a) s[++k] = a;
        }
        for (int i = 1; i <= k; ++i) {
            memset(vis, 0, sizeof(vis));
            dfs(1, i, 0);
        }
        printf("%d\n", sum);
    }
    return 0;
}