UVA 10325：容斥原理計算彩票有效號碼

問題描述

1..N 號碼，給定 M 個數 a_i。刪除所有能被至少一個 a_i 整除的號碼。求剩餘號碼個數。N<2^31, M≤15。

容斥原理

設 A_i = 能被 a_i 整除的數集合。
需求 = N - |∪A_i|。
|∪A_i| = Σ|A_i| - Σ|A_i∩A_j| + Σ|A_i∩A_j∩A_k| - ...
交集 = 能被 LCM 整除。枚舉所有非空子集，計算 LCM，項數 = N / LCM，符號由子集大小奇偶決定。

代碼實現

LL gcd(LL a,LL b){ return b?gcd(b,a%b):a; }
int main() {
    LL n; int m;
    while (cin>>n>>m) {
        vector a(m);
        for (int i=0;i>a[i];
        LL bad=0;
        for (int mask=1; mask<(1<>i&1) {
                lcm = lcm / gcd(lcm,a[i]) * a[i];
                if (lcm>n) { lcm=n+1; break; } // 溢出/超界剪枝
            }
            if (lcm>n) continue;
            if (bits&1) bad += n/lcm;
            else bad -= n/lcm;
        }
        cout << n - bad << endl;
    }
    return 0;
}

關鍵點

• M≤15，子集 2^15=32768，枚舉極快。
• LCM 計算時防溢出：lcm = lcm / gcd * a[i]，若超過 n 直接跳過。
• N 可達 2^31，用 long long。

總結

UVA 10325 是容斥原理標準應用。關鍵在於正確計算子集 LCM 並處理溢出/超界剪枝。模板通用於「計算不被任一給定數整除的數個數」問題。