【概述】

容斥原理是一種較常用的計數方法，其基本思想是：先不考慮重疊的情況，把包含于某內容中的所有對象的數目先計算出來，然后再把計數時重復計算的數目排斥出去，使得計算的結果既無遺漏又無重復。

容斥原理核心的計數規則可以記為一句話：奇加偶減

假設被計數的有 A、B、C 三類，那么，A、B、C 類元素個數總和 = A 類元素個數 + B類元素個數 + C類元素個數 - 既是 A 又是 B 的元素個數 - 既是 A 又是 C 的元素個數 - 既是 B 又是 C 的元素個數 + 既是 A 又是 B 且是 C 的元素個數

即：A∪B∪C = A+B+C - AB - BC - AC?+ ABC

當被計數的種類被推到 n 類時，其統計規則即遵循奇加偶減。

容斥定理最常用于求 [a,b]?區間與?n 互質的數的個數，該問題可視為求 [1,b] 區間與 n 互質的個數減去 [1,a-1] 區間內與 n 互質的個數，故而可先對 n 進行因子分解，然后從 [1,b]、[1,a-1] 區間中減去存在 n 的因子的個數，再根據容斥定理，奇加偶減，對 n 的因子的最小公倍數的個數進行處理即可。

【實例】

一個班級有50名學生，進行一次語數英考試，有9人語文滿分，12人數學滿分，14人英語滿分，又知有6人語文、數學同時滿分，3人語文、英語同時滿分、8人英語、數學同時滿分，還有2人三門課全部滿分，求：沒有一門課滿分的有幾人？至少一門課滿分的有幾人？

由題意知：，且：

沒有一門課滿分的學生集合為：，至少有一門課滿分的學生集合為：

使用容斥原理：

即：

【常見應用】

1.求[a,b]中與n互素的個數

問題可轉換為區間 [1,b] 中與 n 互素的數的個數減去區間 [1,a-1]中與 n 互素的數的個數，那么問題就是轉化為對于 n，求 1~k 中與 n 互質的數有多少個，因此可以先反著來求 1~k 中與 n 不互質的數有多少個。

故對n進行因子分解，然后從1~k中減去不能與n整除的數的個數，然后根據容斥定理奇加偶減，最后答案就是：1~b的元素個數減去1~a-1的元素個數再減去1~b中與n不互質的數的個數加上1~a-1中與n互質的數的個數。

即：b-(a-1)-calculate(b)+calculate(a-1)

bool bprime[N]; LL prime[N],cnt, factor[N],num; void isprime() {//篩素數cnt=0;memset(bprime,false,sizeof(bprime));for(LL i=2; i<N; i++) {if(!bprime[i]) {prime[cnt++]=i;for(LL j=i*i; j<N; j+=i)bprime[i]=true;}} } void getFactor(int n){num=0;for(LL i=0; prime[i]*prime[i]<=n&&i<cnt; i++) {if(n%prime[i]==0) {//記錄n的因子factor[num++]=prime[i];while(n%prime[i]==0)n/=prime[i];}}if(n!=1)//1既不是素數也不是合數factor[num++]=n; } ? LL calculate(LL m,LL num) {LL res=0;for(LL i=1; i<(1<<num); i++) {LL sum=0;LL temp=1;for(LL j=0; j<num; j++) {if(i&(1<<j)) {sum++;temp*=factor[j];}}if(sum%2)res+=m/temp;elseres-=m/temp;}return res; } int main() {isprime();LL a,b,n;scanf("%lld%lld%lld",&a,&b,&n);getFactor(n)//容斥定理，奇加偶減，LL res=(b-(a-1)-calculate(b,num))+calculate(a-1,num);printf("%lld\n",res);return 0; }

?2.求[1,n]中能/不能被m個數整除的個數

對于任意一個數 a[i] 來說，我們能知道在 1-n 中有 n/a[i] 個數是 a[i] 的倍數，但這樣將 m 個數掃一遍一定會用重復的數，因此需要用到容斥原理

根據容斥定理的奇加偶減，對于 m 個數來說，其中的任意 2、4、...、2k 個數就要減去他們最小公倍數能組成的數，1、3、...、2k+1 個數就要加上他們的最小公倍數，因此 m 個數就有 2^m 種情況，對于每種狀態，依次判斷由多少種數組成，然后再進行奇加偶減即可

根據容斥原理有：sum=從 m 中選 1 個數得到的倍數的個數-從 m 中選 2?個數得到的倍數的個數 +?從 m 中選 3?個數得到的倍數的個數 - 從 m 中選 4?個數得到的倍數的個數……

那么能被整除的個數就是 sum，不能被整除的個數就是 n-sum

LL GCD(LL a,LL b){return !b?a:GCD(b,a%b); } LL LCM(LL a,LL b){return a/GCD(a,b)*b; } LL a[N]; int main(){LL n;int m;scanf("%lld%d",&n,&m);for(int i=0;i<m;i++)scanf("%lld",&a[i]);LL sum=0;for(int i=0;i<(1<<m);i++){//2^m種狀態LL lcm=1;LL cnt=0;for(int j=0;j<m;j++){if(i&(1<<j)){//從m中選出j個數lcm=LCM(lcm,a[j]);cnt++;}}if(cnt!=0){if(cnt&1)//奇加sum+=n/lcm;else//偶減sum-=n/lcm;}}printf(%lld "%lld\n",sum,n-sum);return 0; }

【例題】

矩形并的面積（51Nod-2488）(容斥原理)：點擊這里

February 29（LightOJ-1414）(容斥原理+模擬)：點擊這里

Co-prime（HDU-4135）(容斥原理+因子分解)：點擊這里

跳蚤（POJ-1091）(容斥原理+深搜)：點擊這里

Helping Cicada（LightOJ-1117）(容斥原理+二進制枚舉)：點擊這里

How many integers can you find（HDU-1796）(容斥原理+二進制枚舉)：點擊這里

總結

以上是生活随笔為你收集整理的组合数学 —— 容斥定理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。