UVA 10325 The Lottery：容斥原理計算未被篩選號碼數

問題重述

1..N 號碼，給 M 個數（M≤15），刪除所有能被至少一個給定數整除的號碼。求剩餘號碼數。N < 2³¹，多測試用例。

容斥公式

設給定數集為 A。被刪除數 = ∪ 倍數集。容斥：

|∪| = Σ|A_i| - Σ|A_i∩A_j| + Σ|A_i∩A_j∩A_k| - ...
交集為 lcm 的倍數，個數 = N / lcm。
剩餘 = N - |∪|

實現技巧

• M ≤ 15，狀態壓縮枚舉子集（1 << M），共 32767 狀態。
• 預處理 gcd/lcm，防溢出用 `lcm = a / gcd(a,b) * b`，若 lcm > N 直接跳過（貢獻 0）。
• 位數奇/偶決定加/減。

代碼核心

for (int mask=1; mask < (1<>j & 1) {
        lcm = lcm(lcm, a[j]);
        if (lcm > N) { lcm = 0; break; }
    }
    if (lcm) {
        if (bits & 1) ans += N / lcm;
        else ans -= N / lcm;
    }
}
printf("%lld\n", N - ans);

複雜度

每測試用例 O(M·2^M) ≈ 5×10⁵ 操作，極快。

總結

經典容斥 + 狀態壓縮模板題，關鍵在 lcm 溢出處理與大數 N 除法，代碼短小精悍，ACM 必備技能。