容斥原理——這種思想很重要

由于前幾天沒有善待自己的身體，導致我昨天不得不去醫(yī)院檢查一下身體(︶^{︶)，結果醫(yī)生說我是精神上的壓力造成的，這個就讓我很懵逼了，我覺得是我之前飲食不規(guī)律加上熬夜，然后又劇烈運動造成的(︶}︶)，算了，今天吃了藥，感覺好了一點，又來給小伙伴們分享一些小算法了，不過在這還是想提醒大家，身體真的很重要哦(^_)∠※，好的，下面我們切入正題，來看看這個困擾了我一天的容斥定理是個什么鬼

容斥原理的定義：
上中學學集合的時候我們都知道這樣兩個公式：
**A∪B = A+B – A∩B (∩：重合的部分） **
A∪B∪C = A+B+C – A∩B – B∩C – C∩A +A∩B∩C

這兩個公式幫助我們解決了很多以我們當時的邏輯能力很難想開的問題（下面是一些小的例子）：

例1：　一次期末考試，某班有15人數(shù)學得滿分，有12人語文得滿分，并且有4人語、數(shù)都是滿分，那么這個班至少有一門得滿分的同學有多少人？
分析：
依題意，被計數(shù)的事物有語、數(shù)得滿分兩類，“數(shù)學得滿分”稱為“A類元素”，“語文得滿分”稱為“B類元素”，“語、數(shù)都是滿分”稱為“既是A類又是B類的元素”，“至少有一門得滿分的同學”稱為“A類和B類元素個數(shù)”的總和。
答案：
15+12-4=23

**例2：**電視臺向100人調查前一天收看電視的情況，有62人看過2頻道，34人看過8頻道，其中11人兩個頻道都看過。兩個頻道都沒看過的有多少人？
100-（62+34-11）=15

例3：（小學奧數(shù)題）某校六⑴班有學生45人，每人在暑假里都參加體育訓練隊，其中參加足球隊的有25人，參加排球隊的有22人，參加游泳隊的有24人，足球、排球都參加的有12人，足球、游泳都參加的有9人，排球、游泳都參加的有8人，問：三項都參加的有多少人？
分析：
參加足球隊的人數(shù)25人為A類元素，參加排球隊人數(shù)22人為B類元素，參加游泳隊的人數(shù)24人為C類元素，既是A類又是B類的為足球排球都參加的12人，既是B類又C類的為足球游泳都參加的9人，既是C類又是A類的為排球游泳都參加的8人，三項都參加的是A類B類C類的總和設為X。注意：這個題說的每人都參加了體育訓練隊，所以這個班的總人數(shù)即為A類B類和C類的總和。
答案：
25+22+24-12-9-8+X=45 ，解得X=3

例4：（高中題）在1到1000的自然數(shù)中，能被3或5整除的數(shù)共有多少個？不能被3或5整除的數(shù)共有多少個？
分析：
顯然，這是一個重復計數(shù)問題（當然，如果不怕麻煩你可以分別去數(shù)3的倍數(shù)，5的倍數(shù)）。我們可以把“能被3或5整除的數(shù)”分別看成A類元素和B類元素，能“同時被3或5整除的數(shù)（15的倍數(shù)）”就是被重復計算的數(shù)，即“既是A類又是B類的元素”。求的是“A類或B類元素個數(shù)”。我們還不能直接計算，必須先求出所需條件。1000÷3=333……1，能被3整除的數(shù)有333個（想一想，這是為什么？）同理，可以求出其他的條件。

例5：（高中題）分母是1001的最簡分數(shù)一共有多少個？
分析：這一題實際上就是找分子中不能與1001進行約分的數(shù)。由于1001=7×11×13，所以就是找不能被7，11，13整除的數(shù)。
解答：
1~1001中，有7的倍數(shù)1001/7 = 143 （個)；有11的倍數(shù)1001/11 = 91 （個），有13的倍數(shù)1001/13 = 77 （個）；有711=77;77是11的倍數(shù)1001/77 = 13 （個），有713=91;91是13的倍數(shù)；1001/91 = 11 （個），有11*13=143;143是13的倍數(shù)1001/143 = 7 （個）.有1001的倍數(shù)1個。
由容斥原理知：在1~1001中，能被7或11或13整除的數(shù)有（143+91+77）-（13+11+7）+1=281（個），從而不能被7、11或13整除的數(shù)有1001-281=720（個）.也就是說，分母為1001的最簡分數(shù)有720個。

上面的兩個公式其實是容斥原理在要求所并集合很少情況下的公式，那如果所并集合特別多呢？下面讓我們慢慢揭開容斥原理這層神秘的面紗吧(⊙o⊙)

容斥原理是一種重要的組合數(shù)學方法，可以讓你求解任意大小的集合，或者計算復合事件的概率。

容斥原理可以描述如下：
要計算幾個集合并集的大小，我們要先將所有單個集合的大小計算出來，然后減去所有兩個集合相交的部分，再加回所有三個集合相交的部分，再減去所有四個集合相交的部分，依此類推，一直計算到所有集合相交的部分。
上述描述的公式形式可以表示如下：

它可以寫得更簡潔一些，我們將B作為所有Ai的集合，那么容斥原理就變成了：

這個公式是由 **De Moivre (Abraham de Moivre)**提出的。
我們來用維恩圖來表示集合A、B和C：

那么最后的面積就是集合A、B、C各自面積之和減去A與B相交的面積，A與C相交的面積，B與C相交的面積，再加上A、B、C相交的面積。由此，我們也可以解決n個集合求并的問題。

容斥原理的證明：

下面是一些簡單的應用例子：
**例1：**一個簡單的排列問題
由0到9的數(shù)字組成排列，要求第一個數(shù)大于1，最后一個數(shù)小于8，一共有多少種排列？
我們可以來計算它的逆問題，即第一個元素<=1或者最后一個元素>=8的情況。
我們設第一個元素<=1時有X組排列，最后一個元素>=8時有Y組排列。那么通過容斥原理來解決就能夠用到公式：
A∪B = A+B – A∩B (∩：重合的部分）
經過簡單的組合運算，我們得到了結果：

然后被總的排列數(shù)10!減，就是最終的答案了。

**例2：**方程整數(shù)解問題

下面我就以代碼的形式給大家展示一下容斥原理在編程中如何使用的：

注意：在容斥原理中排列組合公式會被經常遇到：

例：求指定區(qū)間內與n互素的數(shù)的個數(shù)

Problem description：

Given a number N, you are asked to count the number of integers between A and B inclusive which are relatively prime to N. Two integers are said to be co-prime or relatively prime if they have no common positive divisors other than 1 or, equivalently, if their greatest common divisor is 1. The number 1 is relatively prime to every integer.

Input

The first line on input contains T (0 < T <= 100) the number of test cases, each of the next T lines contains three integers A, B, N where (1 <= A <= B <= 10 15) and (1 <=N <= 10 9).

Output

For each test case, print the number of integers between A and B inclusive which are relatively prime to N. Follow the output format below.

Sample Input

2
1 10 2
3 15 5

Sample Output

Case #1: 5
Case #2: 10

Hint
In the first test case, the five integers in range [1,10] which are relatively prime to 2 are {1,3,5,7,9}.

這道題的意思是指我先給你一個數(shù)N，然后再給你一個范圍[A,B]，然后讓你找出該區(qū)間內所有和N互質的數(shù)的個數(shù)（不知道什么叫互質的同學，請點擊該鏈接：http://blog.csdn.net/sand8o8time/article/details/76781541），要求先輸入多少組測試數(shù)據(jù)，然后再分別輸入A，B，N，輸出要求是輸出成Case #1: （結果）的形式**(?? . ??)**

舉個例子 [1,10] 區(qū)間中與 6 互素的個數(shù)，應該是 10?(10/2+10/3) 但是這樣多減去了 他們的最小公倍數(shù) 6 的情況，所以在加上 10/6 也就是：
10?(10/2+10/3?10/6)=3
這就用到了容斥原理，知道了這個，題目也就可以做了，先進行素因子分解，然后二進制枚舉子集，再進行容斥原理（奇加偶減）。

看了我之前的博客，或者有一定的數(shù)論基礎的大佬可能會發(fā)現(xiàn)如果所給的范圍是1~n，那么就是歐拉函數(shù)了`(^﹏)′，好的廢話不多說，下面我們來看AC代碼：

#include<iostream> using namespace std; typedef long long LL; const int Max = 1000010; int primeFactor[Max]; int primeNum; LL A,B,N; void ergFac(int n) {primeNum = 0;for(int i = 2;i*i<=n;i++){//只需要算到前根號n項即可，之前在歐拉函數(shù)中已經解釋過，具體的請參看我的歐拉函數(shù)代碼中的注釋 if(n%i==0){ //這里的找質因子的處理方法不是很好，之前的歐拉函數(shù)模板中有更好的處理方法 primeFactor[primeNum++]=i; while(n%i==0) //這個循環(huán)的作用是把n中所有的質因子都除掉，比如12就有2個2的質因子和1個3質因子 n/=i;}}if(n>1) primeFactor[primeNum++]=n; //因為i是循環(huán)到根號n（起初的n），所以最后n（最后的n，n是一直在變化的）的值很有可能大于根號n（起初的n），并且為質數(shù) } LL solve(LL y) {LL ans=0; //這個ans是用來記錄1~y中所有和n不互質的數(shù)得的個數(shù) for(LL i=1;i<(1<<primeNum);i++){ // i<(1<<primeNum)這個是不是感覺很神奇？我也想了好一會才想明白，這個相當于i<2^k,這個源于組合數(shù)學中的排列組合(在)，Ck,1 Ck,2````Ck,k ,沒有Ck,0的原因是有k個因子，至少要選一個作為因子吧 LL ant=0; //ant是用來記錄使用了多少個質因子 LL q=1; //q是用來記錄使用的所有的質因子的乘積 for (LL j=0;j<primeNum;j++){ //j是用來做位運算的，第一層循環(huán)中我們發(fā)現(xiàn) i<(1<<primeNum) if(i&(1<<j)){ //看代碼末尾ant++;q*=primeFactor[j];}}if(ant&1) ans+=y/q; //這個是容斥原理中的容斥原理（奇加偶減） else ans-=y/q; }return ans; } int main() {int t,flag=0;cin>>t; while(t--){cin>>A>>B>>N;ergFac(N);cout<<"Case #"<<++flag<<": "<<B-A+1-solve(B)+solve(A-1)<<endl;} return 0; } //這個地方讀者可以拿幾組數(shù)據(jù)自己來調一調，理解的更快一點，這個是用來判斷 ，主要是用來判斷 從primeNum中選幾個質因子相乘得q ，位運算很容易給大家整暈哈，但是用起來很是靈活 ，比如題目上的第二組測試數(shù)據(jù)，primeNum = 1，為2，那么i=1時能夠判斷i<(1<<primeNum),也就是說只有從1個數(shù)中取一個的情況,如果primeNum = 2，那么就有從2個中取1個，和2個中取2個的情況，一共有3中情況 (2個中取1個d的是兩種)

總結

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

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