容斥原理：
轉載自：https://blog.csdn.net/love20165104027/article/details/81366047
計算幾個集合并集的大小，計算單個元素的集合大小減去兩個集合的相交的部分，加上三個集合相交的部分
減去四個集合相交的部分，一直到所有集合相交的部分；(将可能發生重疊的事情進行不重複的統計)
現在有n件事情，并且每一件對于答案都有着貢獻，但是這n件事情可能會發生重疊，容斥原理的作用就在于不重複的統計
所有對答案有着貢獻的情況的值,具體實作如圖所示
當然也可以将容斥原理表示的更加仔細一點：
容斥原理的應用：
1.機率論：統計發生一件事情的機率，減去發生兩件事情的機率加上發生三件事情的機率......
2.排列組合：統計由0~9構成的數列中首位大于1以及末尾小于8的數列的個數；（數列的限制分為了可能會造成重合的兩種情況）
3.（0,1,2）序列問題：長度為n的由數字0,1,2組成的序列，要求每個數字至少出現一次，求這種序列的個數
我們轉向它的逆問題，即所有的數字均不出現的序列，這樣我們就可以用容斥原理求出不出現0的序列種樹，不出現1的序列種數以此類推
公式最終如圖所示。
并且這道題告訴我們的是容斥原理會與原問題的更簡單的逆問題相結合：方程正整數解,區間内與n互素的數就是容斥原理與逆問題的應用；
4.和睦數三元組的個數問題
給出一個整數
。選出a, b, c (其中2<=a<b<c<=n)，組成和睦三元組，即：
或者滿足
，
，
· 或者滿足
首先，我們考慮它的逆問題：也就是不和睦三元組的個數。
然後，我們可以發現，在每個不和睦三元組的三個元素中，我們都能找到正好兩個元素滿足：它與一個元素互素，并且與另一個元素不互素。
是以，我們隻需枚舉2到n的所有數，将每個數的與其互素的數的個數和與其不互素的數的個數相乘，最後求和并除以2，就是要求的逆問題的答案。
現在我們要考慮這個問題，如何求與2到n這些數互素（不互素）的數的個數。雖然求解與一個數互素數的個數的解法在前面已經提到過了，但在此并不合适，因為 現在要求2到n所有數的結果，分别求解顯然效率太低。
是以，我們需要一個更快的算法，可以一次算出2到n所有數的結果。
在這裡，我們可以使用改進的埃拉托色尼篩法。
· 首先，對于2到n的所有數，我們要知道構成它的素數中是否有次數大于1的，為了應用容斥原理，我們還有知道它們由多少種不同的素數構成。
對于這個問題，我們定義數組deg[i]：表示i由多少種不同素數構成，以及good[i]：取值true或false，表示i包含素數的次數小于等于1是否成立。
再利用埃拉托色尼篩法，在周遊到某個素數i時，枚舉它在2到n範圍内的所有倍數，更新這些倍數的deg[]值，如果有倍數包含了多個i，那麼就把這個倍數的good[]值 賦為false。
· 然後，利用容斥原理，求出2到n每個數的cnt[i]：在2到n中不與i互素的數的個數。
回想容斥原理的公式，它所求的集合是不會包含重複元素的。也就是如果這個集合包含的某個素數多于一次，它們不應再被考慮。
是以隻有當一個數i滿足good[i]=true時，它才會被用于容斥原理。枚舉i的所有倍數i*j，那麼對于i*j，就有N/i個與i*j同樣包含i（素數集合）的數。将這些結果進行加 減，符号由deg[i]（素數集合的大小）決定。如果deg[i]為奇數，那麼我們要用加号，否則用減号。